Submission #548640

#	Time	Username	Problem	Language	Result	Execution time	Memory
548640		ac2hu	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	521 ms	150160 KiB

apple

#include <bits/stdc++.h>
#ifdef DEBUG
#include "../templates/debug.h"
#else 
#define deb(x...)
#endif
using namespace std;
struct node{
    int sum,tl,tr, child[2];
    bool lazy;
    void set(int l,int r){
		sum = 0;
		lazy = false;
		tl =l,tr =r;
		child[0] = child[1] = -1;
    }
};
int cnt = 2;
node t[(int)1e7];
void create(int v){
    if(t[v].tl >= t[v].tr)return;
    int tm = (t[v].tl + t[v].tr)/2;
    if(t[v].child[0] == -1){
		t[v].child[0] = cnt++;
		t[t[v].child[0]].set(t[v].tl,tm);
    }
    if(t[v].child[1] == -1){
		t[v].child[1] = cnt++;
		t[t[v].child[1]].set(tm + 1, t[v].tr);
    }
}
void push(int v){
    create(v);
    if(t[v].tl >= t[v].tr || !t[v].lazy)return;
    t[t[v].child[0]].lazy = 1;
    t[t[v].child[0]].sum = t[t[v].child[0]].tr - t[t[v].child[0]].tl + 1;
    t[t[v].child[1]].lazy = 1;
    t[t[v].child[1]].sum = t[t[v].child[1]].tr - t[t[v].child[1]].tl + 1;
    t[v].lazy = 0;
}
void update(int l,int r,int v){
    if(l > r)return;
    push(v);
    if(l == t[v].tl && r == t[v].tr){
		t[v].lazy = 1;
		t[v].sum = t[v].tr - t[v].tl + 1;
    }
    else{
		int tm = (t[v].tl + t[v].tr)/2;
		update(l, min(r, tm), t[v].child[0]);
		update(max(l,tm + 1), r, t[v].child[1]);
		t[v].sum = t[t[v].child[0]].sum + t[t[v].child[1]].sum;
    }
}
int query(int l,int r,int v){
	// deb(l,r, v);
    if(l > r)return 0;
    push(v);
    if(l == t[v].tl && r == t[v].tr)
		return t[v].sum;
    else{
		int tm = (t[v].tl + t[v].tr)/2;
		return query(l,min(r,tm), t[v].child[0]) + query(max(l,tm + 1), r, t[v].child[1]);
    }
}
int main(){
    t[1].set(1, 1e9);
    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,1)) << "\n";
		}
		else{
	    	update(x,y,1);
		}
    }
}

• Subtask 1: 100 / 100