Submission #538285

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
538285	2022-03-16T13:33:52 Z	fcw	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	495 ms	133316 KB

apple

#include <bits/stdc++.h>
#define st first
#define nd second
using lint = int64_t;
constexpr int mod = int(1e9) + 7;
constexpr int inf = 0x3f3f3f3f;
constexpr int ninf = 0xcfcfcfcf;
constexpr lint linf = 0x3f3f3f3f3f3f3f3f;
const long double pi = acosl(-1.0);
// Returns -1 if a < b, 0 if a = b and 1 if a > b.
int cmp_double(double a, double b = 0, double eps = 1e-9) {
	return a + eps > b ? b + eps > a ? 0 : 1 : -1;
}
using namespace std;


struct node{
	int sum, lz, l, r;
	node(): sum(0), lz(0), l(0), r(0) {}
};

vector<node>seg;

int create(){
	seg.push_back(node());
	return seg.size() - 1;
}

void push(int v, int l, int r){
	if(seg[v].lz){
		seg[v].sum = (r - l + 1) * seg[v].lz;
		if(!seg[v].l) seg[v].l = create();
		if(!seg[v].r) seg[v].r = create();
		seg[seg[v].l].lz = seg[seg[v].r].lz = 1;
		seg[v].lz = 0;
	}
}


void update(int v, int l, int r, int a, int b, int val){
	if(b < l || r < a) return;
	push(v, l, r);
	if(a <= l && r <= b){
		seg[v].lz = 1;
		push(v, l, r);
		return;
	}
	int m = (l + r) >> 1;
	if(!seg[v].l) seg[v].l = create();
	if(!seg[v].r) seg[v].r = create();
	update(seg[v].l, l, m, a, b, val);
	update(seg[v].r, m+1, r, a, b, val);
	push(seg[v].l, l, m);
	push(seg[v].r, m+1, r);
	seg[v].sum = seg[seg[v].l].sum + seg[seg[v].r].sum;
}

int query(int v, int l, int r, int a, int b){
	if(b < l || r < a) return 0;
	if(v == 0) return 0;
	push(v, l, r);
	if(a <= l && r <= b){
		return seg[v].sum;
	}
	int m = (l + r) >> 1;
	return query(seg[v].l, l, m, a, b) + query(seg[v].r, m+1, r, a, b);
}

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	create();
	create();
	int q;
	cin>>q;
	int c = 0;
	for(int i=0;i<q;i++){
		int op, x, y;
		cin>>op>>x>>y;
		if(op == 2) update(1, 1, int(1e9 + 7), x + c, y + c, 1);
		else{
			int cnt = query(1, 1, int(1e9 + 7), x + c, y + c);
			cout<<cnt<<"\n";
			c = cnt;
		}
	}


	return 0;
}
/*
[  ]Leu o problema certo???
[  ]Ver se precisa de long long
[  ]Viu o limite dos fors (é n? é m?)
[  ]Tamanho do vetor, será que é 2e5 em vez de 1e5??
[  ]Testar sample
[  ]Testar casos de  borda
[  ]1LL no 1LL << i
[  ]Testar mod (é 1e9+7, mesmo?, será que o mod não ficou negativo?)
*/

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	17 ms	4672 KB	Output is correct
5	Correct	19 ms	4676 KB	Output is correct
6	Correct	19 ms	4640 KB	Output is correct
7	Correct	20 ms	4684 KB	Output is correct
8	Correct	144 ms	33936 KB	Output is correct
9	Correct	301 ms	67680 KB	Output is correct
10	Correct	341 ms	67572 KB	Output is correct
11	Correct	342 ms	67428 KB	Output is correct
12	Correct	319 ms	67332 KB	Output is correct
13	Correct	305 ms	67388 KB	Output is correct
14	Correct	305 ms	67396 KB	Output is correct
15	Correct	435 ms	133204 KB	Output is correct
16	Correct	495 ms	133316 KB	Output is correct
17	Correct	296 ms	68644 KB	Output is correct
18	Correct	323 ms	68492 KB	Output is correct
19	Correct	440 ms	133272 KB	Output is correct
20	Correct	461 ms	133168 KB	Output is correct