Advertisement
Guest User

Untitled

a guest
Mar 22nd, 2019
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.63 KB | None | 0 0
  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<cstdlib>
  4. #include<iostream>
  5. #include<cstring>
  6. #include<vector>
  7. using namespace std;
  8. const int N=3000006;
  9. struct nd{int l,r,t,id;}rec[N];
  10. int ans[1000006],tab[N];
  11. int R[N*3],ID[N*3],T[N*3];
  12. inline bool cmp(nd a,nd b) {
  13. if(a.l!=b.l) return a.l<b.l;
  14. if(a.t!=b.t) return a.t>b.t;
  15. return a.id<b.id;
  16. }
  17. inline void insert(int x,int l,int r,nd y) {
  18. if(l==r) {
  19. R[x]=y.r;
  20. ID[x]=y.id;
  21. return;
  22. }
  23. int mid=(l+r)>>1;
  24. if(y.t<=mid) insert(x<<1,l,mid,y);
  25. else insert(x<<1|1,mid+1,r,y);
  26. R[x]=max(R[x<<1],R[x<<1|1]);
  27. }
  28. inline int query(int x,int l,int r,int pos,int lim) {
  29. if(R[x]<lim) return -1;
  30. if(l==r) return ID[x];
  31. int mid=(l+r)>>1,ret=-1;
  32. if(pos<=mid) {
  33. ret=query(x<<1,l,mid,pos,lim);
  34. if(ret>0) return ret;
  35. }
  36. return query(x<<1|1,mid+1,r,pos,lim);
  37. }
  38. int main() {
  39. int n,m,all;
  40. scanf("%d%d",&n,&m);
  41. all=m+n;
  42. for(int i=1;i<=all;i++) {
  43. scanf("%d%d%d",&rec[i].l,&rec[i].r,&rec[i].t);
  44. tab[i]=rec[i].t;
  45. rec[i].id=i;
  46. }
  47. sort(rec+1,rec+all+1,cmp);
  48. sort(tab+1,tab+all+1);
  49.  
  50. for(int i=1;i<=all;i++) {
  51. rec[i].t=lower_bound(tab+1,tab+all+1,rec[i].t)-tab;
  52. if(rec[i].id<=n) insert(1,1,all,rec[i]);
  53. else ans[rec[i].id-n]=query(1,1,all,rec[i].t,rec[i].r);
  54. }
  55. for(int i=1;i<=m;i++) printf("%d ",ans[i]);
  56. return 0;
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement