Submission #442054

#	Time	Username	Problem	Language	Result	Execution time	Memory
442054		penguinhacker	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	418 ms	96320 KiB

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 / 100