Submission #442053

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
442053	2021-07-06T23:50:33 Z	penguinhacker	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	445 ms	171224 KB

apple

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

#define ll long long
#define ar array

const int mxQ=1e5, MX=1e9, mxN=66*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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	14 ms	2304 KB	Output is correct
5	Correct	17 ms	2684 KB	Output is correct
6	Correct	17 ms	2636 KB	Output is correct
7	Correct	17 ms	2808 KB	Output is correct
8	Correct	133 ms	19120 KB	Output is correct
9	Correct	291 ms	32580 KB	Output is correct
10	Correct	312 ms	36436 KB	Output is correct
11	Correct	304 ms	39288 KB	Output is correct
12	Correct	313 ms	40776 KB	Output is correct
13	Correct	273 ms	49656 KB	Output is correct
14	Correct	275 ms	50392 KB	Output is correct
15	Runtime error	445 ms	171224 KB	Execution killed with signal 6
16	Halted	0 ms	0 KB	-