Submission #548631

#	Time	Username	Problem	Language	Result	Execution time	Memory
548631		ac2hu	원숭이와 사과 나무 (IZhO12_apple)	C++14	0 / 100	584 ms	262144 KiB

apple

#include<bits/stdc++.h>
using namespace std;
struct node{
    node* child[2];
    int lazy, sum;
    int tl,tr;
};
node* make_node(int tl,int tr){
    node* temp = new node;
    for(int i = 0;i<2;i++)
	temp->child[i] = NULL;
    temp-> tl = tl;
    temp-> tr = tr;
    temp->lazy = 0;
    temp->sum = 0;
    return temp;
}
node* pull(node *temp){
    temp->sum = temp->child[0]->sum + temp->child[1]->sum;
    temp->lazy = 0;
    return temp;
}
node* push(node* v){
    if(v->lazy == 0 || v->tl == v->tr)return v;    
    int tm = (v->tl + v->tr)/2;
    if(!v->child[0])
	v->child[0] = make_node(v->tl, tm);
    if(!v->child[1])
	v->child[1] = make_node(tm + 1, v->tr);
    v->child[1]->lazy = v->child[0]->lazy = 1;
    v->child[0]->sum = tm - v->tl + 1;
    v->child[1]->sum = v->tr - tm;
    return v;
}
void update(int l,int r,node *v){
    v = push(v);
    if(l > r)
	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;
	if(!v->child[0])
	    v->child[0] = make_node(v->tl, tm);
	if(!v->child[1])
	    v->child[1] = make_node(tm + 1, v->tr);
	update(l, min(tm,r), v->child[0]);
	update(max(l,tm + 1), r, v->child[1]);
	v = pull(v);
    }
}
int query(int l,int r,node* v){
    v = push(v);
    if(l > r)
	return 0;
    else if(l == v->tl && r == v->tr)
	return v->sum;
    else{
	int tm = (v->tl + v->tr)/2;
	if(!v->child[0])
	    v->child[0] = make_node(v->tl, tm);
	if(!v->child[1])
	    v->child[1] = make_node(tm + 1, v->tr);
	return query(l, min(tm, r), v->child[0]) + query(max(l,tm + 1), r, v->child[1]);
    }
}
int main(){
    node* root = make_node(0, 1e9 + 100);
    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);
	}
    }
}

• Subtask 1: 0 / 100