Advertisement
STEFAN_STOYANOV

beatle

Feb 1st, 2023
35
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.40 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define endl"\n"
  3.  
  4. using namespace std;
  5. const int maxn=(1<<17),maxx=1e5;
  6. struct segtree{
  7. int pl,lazy,cnt;
  8. segtree(){
  9. pl=-1;
  10. lazy=0;
  11. cnt=0;
  12. }
  13. void output(){
  14. cout<<pl<<" "<<lazy<<" "<<cnt<<"\n";
  15. }
  16. };
  17. struct plank{
  18. int x,y,d;
  19. plank(){
  20. x=0;
  21. y=0;
  22. d=0;
  23. }
  24. plank(int _x, int _y, int _d){
  25. x= _x;
  26. y= _y;
  27. d =_d;
  28. }
  29. bool operator<(const plank &pl)const{
  30. return y<pl.y;
  31. }
  32. void input(){
  33. cin>>x>>y>>d;
  34. }
  35. void output(){
  36. cout<<x<<" "<<y<<" "<<d<<"\n";
  37. }
  38. };
  39. int n;
  40. plank a[maxn];
  41. segtree t[maxn*2];
  42. int reallvl[maxn];
  43. int *lvl;
  44. void push_lazy(int i, int l, int r){
  45. /*t[i].cnt+=t[i].lazy;
  46. t[i*2].lazy+=t[i].lazy;
  47. t[i*2+1].lazy+=t[i].lazy;
  48. t[i].lazy=0;*/
  49. if(t[i].pl>t[i*2].pl)
  50. t[i*2].pl=t[i].pl;
  51. if(t[i].pl>t[i*2+1].pl)
  52. t[i*2+1].pl=t[i].pl;
  53. }
  54.  
  55. int query(int i, int l, int r, int pos){
  56. push_lazy(i,l,r);
  57. if(l==r){
  58. return t[i].pl;
  59. }
  60. int mid=(l+r)/2;
  61. if(pos<=mid)
  62. return query(i*2,l,mid,pos);
  63. return query(i*2+1,mid+1,r,pos);
  64. }
  65.  
  66. void update(int i, int l, int r, int ql, int qr, int pl){
  67. //cout<<"i=="<<i<<" l=="<<l<<" r=="<<r<<" ql=="<<ql<<" qr=="<<qr<<" pl=="<<pl<<"\n";
  68. if(l>r)return;
  69. //cout<<"l<=r\n";
  70. push_lazy(i,l,r);
  71. //cout<<"pushed lazy\n";
  72. if(r<ql||l>qr){
  73. //cout<<"1st bound of stopping\n";
  74. return;
  75. }
  76. //cout<<"it is not out the interval\n";
  77. if(ql<=l&&r<=qr){
  78. //cout<<"it is covered by the interval\n";
  79. /*int pl1,pl2,m;
  80. pl1=query(1,1,maxx,a[pl].x-1);
  81. pl2=query(1,1,maxx,a[pl].x+a[pl].d);
  82. cout<<"init lvl of the pl\n";
  83. cout<<pl<<" "<<pl1<<" "<<pl2<<" "<<lvl[pl1]<<" "<<lvl[pl2]<<"\n";
  84. m=min(lvl[pl1],lvl[pl2]);
  85. lvl[pl]=m+1;*/
  86. if(l==a[pl].x){
  87. int hpl=query(1,1,maxx,a[pl].x-1);
  88. if(lvl[pl]==0||lvl[pl]>lvl[hpl]+1)
  89. lvl[pl]=lvl[hpl]+1;
  90. }
  91. if(r==a[pl].x+a[pl].d){
  92. int hlp=query(1,1,maxx,a[pl].x+a[pl].d);
  93. if(lvl[pl]==0||lvl[pl]>lvl[hlp]+1)
  94. lvl[pl]=lvl[hlp]+1;
  95. }
  96. t[i].lazy++;
  97. t[i].pl=pl;
  98. push_lazy(i,l,r);
  99. return;
  100. }
  101. //cout<<"Nor fully in it\n";
  102. int mid=(l+r)/2;
  103. update(i*2,l,mid,ql,qr,pl);
  104. update(i*2+1,mid+1,r,ql,qr,pl);
  105. }
  106.  
  107. /*void update(int i, int l, int r, int ql, int qr, int pl){
  108.  
  109. }*/
  110.  
  111. void everyleaf(int i,int l,int r){
  112. push_lazy(i,l,r);
  113. if(l==r){
  114. if(l<=20)t[i].output();
  115. return;
  116. }
  117. int mid=(l+r)/2;
  118. everyleaf(i*2,l,mid);
  119. everyleaf(i*2+1,mid+1,r);
  120. }
  121.  
  122. int main()
  123. {
  124. /*ios_base::sync_with_stdio(false);
  125. cin.tie(0);
  126. cout.tie(0);*/
  127. lvl=reallvl+1;
  128. cin>>n;
  129. for(int i=0;i<n;++i)
  130. a[i].input();
  131. sort(a,a+n);
  132. cout<<"\n";
  133. for(int i=0;i<n;++i){
  134. update(1,1,maxx,a[i].x,a[i].x+a[i].d-1,i);
  135. //cout<<"updated "<<i<<"th plank\n";
  136. cout<<i<<" ";
  137. a[i].output();
  138. }
  139.  
  140. //cout<<"Updating passed\n";
  141. //everyleaf(1,1,maxx);
  142. int t,pos,pl;
  143. cin>>t;
  144. while(t){
  145. cin>>pos;
  146. pl=query(1,1,maxx,pos);
  147. cout<<pl<<" ";
  148. cout<<lvl[pl]<<"\n";
  149. --t;
  150. }
  151. return 0;
  152. }
  153.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement