Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<cstdio>
- #include<algorithm>
- #include<cstdlib>
- #include<iostream>
- #include<cstring>
- #include<vector>
- using namespace std;
- const int N=3000006;
- struct nd{int l,r,t,id;}rec[N];
- int ans[1000006],tab[N];
- int R[N*3],ID[N*3],T[N*3];
- inline bool cmp(nd a,nd b) {
- if(a.l!=b.l) return a.l<b.l;
- if(a.t!=b.t) return a.t>b.t;
- return a.id<b.id;
- }
- inline void insert(int x,int l,int r,nd y) {
- if(l==r) {
- R[x]=y.r;
- ID[x]=y.id;
- return;
- }
- int mid=(l+r)>>1;
- if(y.t<=mid) insert(x<<1,l,mid,y);
- else insert(x<<1|1,mid+1,r,y);
- R[x]=max(R[x<<1],R[x<<1|1]);
- }
- inline int query(int x,int l,int r,int pos,int lim) {
- if(R[x]<lim) return -1;
- if(l==r) return ID[x];
- int mid=(l+r)>>1,ret=-1;
- if(pos<=mid) {
- ret=query(x<<1,l,mid,pos,lim);
- if(ret>0) return ret;
- }
- return query(x<<1|1,mid+1,r,pos,lim);
- }
- int main() {
- int n,m,all;
- scanf("%d%d",&n,&m);
- all=m+n;
- for(int i=1;i<=all;i++) {
- scanf("%d%d%d",&rec[i].l,&rec[i].r,&rec[i].t);
- tab[i]=rec[i].t;
- rec[i].id=i;
- }
- sort(rec+1,rec+all+1,cmp);
- sort(tab+1,tab+all+1);
- for(int i=1;i<=all;i++) {
- rec[i].t=lower_bound(tab+1,tab+all+1,rec[i].t)-tab;
- if(rec[i].id<=n) insert(1,1,all,rec[i]);
- else ans[rec[i].id-n]=query(1,1,all,rec[i].t,rec[i].r);
- }
- for(int i=1;i<=m;i++) printf("%d ",ans[i]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement