Submission #442052

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
442052	2021-07-06T23:48:29 Z	penguinhacker	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	489 ms	165416 KB

apple

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

#define ll long long
#define ar array

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

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) {
	//cout << "[" << l << ", " << r << "]\n";
	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]];
	//cout << "[" << l << ", " << r << "] = " << st[u] << endl;
}

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<=63*mxQ);
	}
	return 0;
}

Subtask #1

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	2504 KB	Output is correct
5	Correct	18 ms	2976 KB	Output is correct
6	Correct	21 ms	2840 KB	Output is correct
7	Correct	22 ms	2956 KB	Output is correct
8	Correct	147 ms	19992 KB	Output is correct
9	Correct	307 ms	34372 KB	Output is correct
10	Correct	310 ms	38212 KB	Output is correct
11	Correct	325 ms	41212 KB	Output is correct
12	Correct	320 ms	42492 KB	Output is correct
13	Correct	297 ms	51716 KB	Output is correct
14	Correct	278 ms	52296 KB	Output is correct
15	Runtime error	489 ms	165416 KB	Execution killed with signal 6
16	Halted	0 ms	0 KB	-