Submission #442054

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
442054	2021-07-06T23:51:43 Z	penguinhacker	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	418 ms	96320 KB

apple

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxQ=1e5, MX=1e9, mxN=121*mxQ;
int n=1, q, ans, st[mxN], lc[mxN], rc[mxN];
bool lz[mxN];

void ex(int u) {
	if (!lc[u])
		lc[u]=++n;
	if (!rc[u])
		rc[u]=++n;
}

void psh(int u, int l, int r) {
	if (lz[u]) {
		st[u]=r-l+1;
		if (l^r) {
			ex(u);
			lz[lc[u]]=1, lz[rc[u]]=1;
		}
		lz[u]=0;
	}
}

void upd(int ql, int qr, int u=1, int l=1, int r=MX) {
	psh(u, l, r);
	if (ql<=l&&r<=qr) {
		lz[u]=1;
		psh(u, l, r);
		return;
	}
	int mid=(l+r)/2;
	ex(u);
	if (ql<=mid)
		upd(ql, qr, lc[u], l, mid);
	if (qr>mid)
		upd(ql, qr, rc[u], mid+1, r);
	psh(lc[u], l, mid);
	psh(rc[u], mid+1, r);
	st[u]=st[lc[u]]+st[rc[u]];
}

int qry(int ql, int qr, int u=1, int l=1, int r=MX) {
	psh(u, l, r);
	if (ql<=l&&r<=qr)
		return st[u];
	int mid=(l+r)/2, res=0;
	if (ql<=mid) {
		if (!lc[u])
			lc[u]=++n;
		res+=qry(ql, qr, lc[u], l, mid);
	}
	if (qr>mid) {
		if (!rc[u])
			rc[u]=++n;
		res+=qry(ql, qr, rc[u], mid+1, r);
	}
	return res;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> q;
	while(q--) {
		int t, l, r;
		cin >> t >> l >> r;
		l+=ans, r+=ans;
		if (t==1) // query
			cout << (ans=qry(l, r)) << "\n";
		else
			upd(l, r);
		assert(n<mxN-200);
	}
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	15 ms	2380 KB	Output is correct
5	Correct	17 ms	2728 KB	Output is correct
6	Correct	21 ms	2620 KB	Output is correct
7	Correct	17 ms	2708 KB	Output is correct
8	Correct	129 ms	19108 KB	Output is correct
9	Correct	301 ms	32500 KB	Output is correct
10	Correct	288 ms	36388 KB	Output is correct
11	Correct	298 ms	39400 KB	Output is correct
12	Correct	306 ms	40648 KB	Output is correct
13	Correct	271 ms	49600 KB	Output is correct
14	Correct	278 ms	50288 KB	Output is correct
15	Correct	392 ms	91392 KB	Output is correct
16	Correct	418 ms	94348 KB	Output is correct
17	Correct	269 ms	54084 KB	Output is correct
18	Correct	290 ms	54084 KB	Output is correct
19	Correct	398 ms	96296 KB	Output is correct
20	Correct	393 ms	96320 KB	Output is correct