[TIOJ] 1223. 好想睡覺 之 好累的大頭蕃 EX
題目連結:http://tioj.infor.org/problems/1223
前面一直狂WA,但總覺得我的想法沒有錯,最後才發現是某個小地方做錯了QQ
想法大概就是把原本不行的區間轉成可以的區間,然後塞到線段樹,其中線段樹維護的是每個點往右最遠可以到哪裡,並且記錄一下是在第幾號的時候有最遠,那查詢也變得很容易,因為就只要單點查那個點最遠可以到哪裡就好了。
把步行區間轉可以區間的部分是害我一直WA掉的點,原本以為轉法就是排序好一堆$[L_i, R_i)$,接著看$[R_{i-1}, L_i]$是否合法($ R_{i-1} < L_i $)即可,但是其實不能只看$R_{i-1}$而是要看$\displaystyle \max_{1 \leq k < i}R_k$。
另外線段樹的部分因為最後是要取最大值,修改也都是取最大值,所以其實可以直接在節點上修改,然後詢問時把路徑上的所有節點取max就好。
p.s 值域有點大所以要先離散化
前面一直狂WA,但總覺得我的想法沒有錯,最後才發現是某個小地方做錯了QQ
想法大概就是把原本不行的區間轉成可以的區間,然後塞到線段樹,其中線段樹維護的是每個點往右最遠可以到哪裡,並且記錄一下是在第幾號的時候有最遠,那查詢也變得很容易,因為就只要單點查那個點最遠可以到哪裡就好了。
把步行區間轉可以區間的部分是害我一直WA掉的點,原本以為轉法就是排序好一堆$[L_i, R_i)$,接著看$[R_{i-1}, L_i]$是否合法($ R_{i-1} < L_i $)即可,但是其實不能只看$R_{i-1}$而是要看$\displaystyle \max_{1 \leq k < i}R_k$。
另外線段樹的部分因為最後是要取最大值,修改也都是取最大值,所以其實可以直接在節點上修改,然後詢問時把路徑上的所有節點取max就好。
p.s 值域有點大所以要先離散化
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define FF first
#define SS second
#define PB push_back
#define ALL(x) (x).begin(), (x).end()
const int N = 100000 + 10;
class LiSan{
private:
vector<int> v;
public:
inline void init(){v.clear();}
inline void insert(int x){v.PB(x);}
inline void done(){
sort(ALL(v));
v.resize(distance(v.begin(), unique(ALL(v))));
}
inline int size(){return v.size();}
inline int get(int x){
return distance(v.begin(), lower_bound(ALL(v), x));
}
inline int inv_get(int x){return v[x];}
} lisan;
class SegTree{
private:
PII nodes[4*N];
int size;
inline int lc(int x) const {return 2*x+1;}
inline int rc(int x) const {return 2*x+2;}
void build(int l, int r, int id){
nodes[id] = {-1, -1};
if(r-l > 1){
int mid=(l+r)>>1;
build(l, mid, lc(id));
build(mid, r, rc(id));
}
}
void modify(int ql, int qr, int l, int r,const PII v, int id){
if(qr <= l or r <= ql) return;
if(ql <= l and r <= qr){
if( (nodes[id].SS < v.SS) or \
(nodes[id].SS==v.SS and nodes[id].FF>v.FF) )
nodes[id]=v;
return;
}
int mid=(l+r)>>1;
modify(ql, qr, l, mid, v, lc(id));
modify(ql, qr, mid, r, v, rc(id));
}
PII query(int ql, int qr, int l, int r, int id) const {
if(qr <= l or r <= ql) return {-1, -1};
if(ql <= l and r <= qr) return nodes[id];
int mid=(l+r)>>1;
PII ll = query(ql, qr, l, mid, lc(id));
PII rr = query(ql, qr, mid, r, rc(id));
if( (ll.SS < rr.SS) or \
(ll.SS==rr.SS and ll.FF>rr.FF) )
ll=rr;
if( (ll.SS < nodes[id].SS) or \
(ll.SS==nodes[id].SS and ll.FF>nodes[id].FF) )
ll=nodes[id];
return ll;
}
public:
void build(int s){
size=s;
build(0,s,0);
}
void modify(int l, int r, PII v){
modify(l, r, 0, size, v, 0);
}
PII query(int p){
return query(p, p+1, 0, size, 0);
}
} seg;
inline void init(int);
vector<PII> shine[N];
vector<int> qs;
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n, t;
while(cin>>n>>t, n!=0 or t!=0){
init(n);
int m; cin>>m;
while(m--){
int a, b, c; cin>>a>>b>>c;
shine[a].PB({b, c});
lisan.insert(b);
lisan.insert(c);
}
for(int i=1;i<=n;++i){
shine[i].PB({0, 0});
shine[i].PB({t, t});
}
lisan.insert(0);
lisan.insert(t);
int q; cin>>q;
while(q--){
int x; cin>>x;
qs.PB(x);
lisan.insert(x);
}
lisan.done();
seg.build(lisan.size());
for(int i=1;i<=n;++i){
sort(ALL(shine[i]));
int ll=0;
for(int j=1;j<=(int)shine[i].size();++j){
ll = max(ll, shine[i][j-1].SS);
int rr = shine[i][j].FF;
if(ll<rr) seg.modify(lisan.get(ll), lisan.get(rr)+1, {i,rr});
}
}
for(auto x:qs){
PII res = seg.query(lisan.get(x));
if(res.SS - x <= 0) cout<<"Oh, no!\n";
else cout<<res.FF<<' '<<res.SS-x<<'\n';
}
}
return 0;
}
inline void init(int n){
lisan.init();
qs.clear();
for(int i=1;i<=n;++i) shine[i].clear();
}
留言
張貼留言