Submission #548637

#	Time	Username	Problem	Language	Result	Execution time	Memory
548637		ac2hu	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	530 ms	262144 KiB

apple

#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){
    push(v);
    if(l > r || !v)
	return;
    else 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){
    push(v);
    if(l > r || !v)
	return 0;
    else 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:9: warning: unused variable 'tm' [-Wunused-variable]
   28 |     int tm = (v->tl + v->tr)/2;
      |         ^~

• Subtask 1: 0 / 100