[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 值域有點大所以要先離散化

#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();
}