Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define endl"\n"
- using namespace std;
- const int maxn=(1<<17),maxx=1e5;
- struct segtree{
- int pl,lazy,cnt;
- segtree(){
- pl=-1;
- lazy=0;
- cnt=0;
- }
- void output(){
- cout<<pl<<" "<<lazy<<" "<<cnt<<"\n";
- }
- };
- struct plank{
- int x,y,d;
- plank(){
- x=0;
- y=0;
- d=0;
- }
- plank(int _x, int _y, int _d){
- x= _x;
- y= _y;
- d =_d;
- }
- bool operator<(const plank &pl)const{
- return y<pl.y;
- }
- void input(){
- cin>>x>>y>>d;
- }
- void output(){
- cout<<x<<" "<<y<<" "<<d<<"\n";
- }
- };
- int n;
- plank a[maxn];
- segtree t[maxn*2];
- int reallvl[maxn];
- int *lvl;
- void push_lazy(int i, int l, int r){
- /*t[i].cnt+=t[i].lazy;
- t[i*2].lazy+=t[i].lazy;
- t[i*2+1].lazy+=t[i].lazy;
- t[i].lazy=0;*/
- if(t[i].pl>t[i*2].pl)
- t[i*2].pl=t[i].pl;
- if(t[i].pl>t[i*2+1].pl)
- t[i*2+1].pl=t[i].pl;
- }
- int query(int i, int l, int r, int pos){
- push_lazy(i,l,r);
- if(l==r){
- return t[i].pl;
- }
- int mid=(l+r)/2;
- if(pos<=mid)
- return query(i*2,l,mid,pos);
- return query(i*2+1,mid+1,r,pos);
- }
- void update(int i, int l, int r, int ql, int qr, int pl){
- //cout<<"i=="<<i<<" l=="<<l<<" r=="<<r<<" ql=="<<ql<<" qr=="<<qr<<" pl=="<<pl<<"\n";
- if(l>r)return;
- //cout<<"l<=r\n";
- push_lazy(i,l,r);
- //cout<<"pushed lazy\n";
- if(r<ql||l>qr){
- //cout<<"1st bound of stopping\n";
- return;
- }
- //cout<<"it is not out the interval\n";
- if(ql<=l&&r<=qr){
- //cout<<"it is covered by the interval\n";
- /*int pl1,pl2,m;
- pl1=query(1,1,maxx,a[pl].x-1);
- pl2=query(1,1,maxx,a[pl].x+a[pl].d);
- cout<<"init lvl of the pl\n";
- cout<<pl<<" "<<pl1<<" "<<pl2<<" "<<lvl[pl1]<<" "<<lvl[pl2]<<"\n";
- m=min(lvl[pl1],lvl[pl2]);
- lvl[pl]=m+1;*/
- if(l==a[pl].x){
- int hpl=query(1,1,maxx,a[pl].x-1);
- if(lvl[pl]==0||lvl[pl]>lvl[hpl]+1)
- lvl[pl]=lvl[hpl]+1;
- }
- if(r==a[pl].x+a[pl].d){
- int hlp=query(1,1,maxx,a[pl].x+a[pl].d);
- if(lvl[pl]==0||lvl[pl]>lvl[hlp]+1)
- lvl[pl]=lvl[hlp]+1;
- }
- t[i].lazy++;
- t[i].pl=pl;
- push_lazy(i,l,r);
- return;
- }
- //cout<<"Nor fully in it\n";
- int mid=(l+r)/2;
- update(i*2,l,mid,ql,qr,pl);
- update(i*2+1,mid+1,r,ql,qr,pl);
- }
- /*void update(int i, int l, int r, int ql, int qr, int pl){
- }*/
- void everyleaf(int i,int l,int r){
- push_lazy(i,l,r);
- if(l==r){
- if(l<=20)t[i].output();
- return;
- }
- int mid=(l+r)/2;
- everyleaf(i*2,l,mid);
- everyleaf(i*2+1,mid+1,r);
- }
- int main()
- {
- /*ios_base::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);*/
- lvl=reallvl+1;
- cin>>n;
- for(int i=0;i<n;++i)
- a[i].input();
- sort(a,a+n);
- cout<<"\n";
- for(int i=0;i<n;++i){
- update(1,1,maxx,a[i].x,a[i].x+a[i].d-1,i);
- //cout<<"updated "<<i<<"th plank\n";
- cout<<i<<" ";
- a[i].output();
- }
- //cout<<"Updating passed\n";
- //everyleaf(1,1,maxx);
- int t,pos,pl;
- cin>>t;
- while(t){
- cin>>pos;
- pl=query(1,1,maxx,pos);
- cout<<pl<<" ";
- cout<<lvl[pl]<<"\n";
- --t;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement