Submission #548640

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
548640	2022-04-14T05:14:58 Z	ac2hu	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	521 ms	150160 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	23 ms	3540 KB	Output is correct
5	Correct	29 ms	4260 KB	Output is correct
6	Correct	28 ms	4028 KB	Output is correct
7	Correct	27 ms	4216 KB	Output is correct
8	Correct	171 ms	30720 KB	Output is correct
9	Correct	383 ms	52652 KB	Output is correct
10	Correct	377 ms	58672 KB	Output is correct
11	Correct	399 ms	63296 KB	Output is correct
12	Correct	381 ms	65432 KB	Output is correct
13	Correct	440 ms	79040 KB	Output is correct
14	Correct	384 ms	79704 KB	Output is correct
15	Correct	507 ms	145568 KB	Output is correct
16	Correct	521 ms	146640 KB	Output is correct
17	Correct	402 ms	82536 KB	Output is correct
18	Correct	382 ms	82628 KB	Output is correct
19	Correct	510 ms	150160 KB	Output is correct
20	Correct	515 ms	150092 KB	Output is correct