oj.uz

답안 #442054

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
442054 2021-07-06T23:51:43 Z penguinhacker 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
 418 ms 96320 KB 
#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

# 결과 실행 시간 메모리 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