Submission #548639

#TimeUsernameProblemLanguageResultExecution timeMemory
548639ac2huMonkey and Apple-trees (IZhO12_apple)C++14
0 / 100
605 ms262144 KiB
    #include<bits/stdc++.h>
    using namespace std;
    struct node{
        node* child[2];
        bool lazy;
        int tl,tr,sum;
        node(int l, int r){
    	lazy = 0;
    	sum = 0;
    	tl = l;
    	tr = r;
    	child[0] = child[1] = NULL;
        };
        void add(){
    	int tm = (tl + tr)/2;
    	if(!child[0])
    	   child[0] = new node(tl, tm);
    	if(!child[1])
    	   child[1] = new node(tm + 1, tr);
        }
        int siz(){
    	return tr - tl + 1;
        }
    };
    node *root = new node(1, 1e9);
    void push(node* v){
        if(v->lazy == 0 || v->tl == v->tr)return;
        int tm = (v->tl + v->tr)/2;
        v->add();
        v->child[0]->lazy = 1;
        v->child[1]->lazy = 1;
        v->lazy= 0;
        v->child[0]->sum = v->child[0]->siz();
        v->child[1]->sum = v->child[1]->siz();
    }
    void update(int l,int r,node *v){
        if(l > r || !v)
    	return;
        push(v);
        if(l <= v->tl && r >= v->tr){
    	int siz = v->tr - v->tl + 1;
    	v->lazy = 1;
    	v->sum = siz;
        }
        else{
    	int tm = (v->tl + v->tr)/2;
    	v->add();
    	if(l > tm){
    	    update(l, r, v->child[1]);
    	}
    	else if(r <= tm){
    	    update(l,r, v->child[0]);
    	}
    	else{
    	    update(l, min(tm,r), v->child[0]);
    	    update(max(l,tm + 1), r, v->child[1]);
    	}
    	v->sum = v->child[0]->sum + v->child[1]->sum;
        }
    }
    int query(int l,int r,node* v){
        if(l > r || !v)
    	return 0;
        push(v);
        if(l <= v->tl && r >= v->tr){
    	return v->sum;
        }
        else{
    	int tm = (v->tl + v->tr)/2;
    	v->add();
    	return query(l, min(tm, r), v->child[0]) + query(max(l,tm + 1), r, v->child[1]);
    	if(l > tm){
    	    return query(l, r, v->child[1]);
    	}
    	else if(r <= tm){
    	    return query(l,r, v->child[0]);
    	}
    	else{
    	    return query(l, min(tm,r), v->child[0]) + query(max(l,tm + 1), r, v->child[1]);
    	}
        }
    }
    int main(){
        int q;cin >> q;
        int c = 0;
        while(q--){
    	int d, x, y;cin >> d >> x >> y;
    	x += c;y+=c;
    	if(d == 1){
    	    cout << (c = query(x,y,root)) << "\n";
    	}
    	else{
    	    update(x,y,root);
    	}
        }
    }

Compilation message (stderr)

apple.cpp: In function 'void push(node*)':
apple.cpp:28:13: warning: unused variable 'tm' [-Wunused-variable]
   28 |         int tm = (v->tl + v->tr)/2;
      |             ^~
#Verdict Execution timeMemoryGrader output
Fetching results...