제출 #548633

#제출 시각아이디문제언어결과실행 시간메모리
548633ac2huMonkey and Apple-trees (IZhO12_apple)C++14
0 / 100
535 ms262144 KiB
#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;
}
void pull(node *temp){
    temp->sum = temp->child[0]->sum + temp->child[1]->sum;
    temp->lazy = 0;
}
void push(node* v){
    if(v->lazy == 0 || v->tl == v->tr)return;
    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;
}
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;
	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]);
	pull(v);
    }
}
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;
	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);
	}
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...