답안 #915831

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
915831	2024-01-24T18:45:25 Z	Nonoze	원숭이와 사과 나무 (IZhO12_apple)	C++17	100 / 100	354 ms	188520 KB

apple

#include <bits/stdc++.h>

//#define int long long
#define sz(x) (int)(x.size())
#define debug(x) cerr << (#x) << ": " << (x) << endl

using namespace std;

struct node
{
	int left, right;
	int sum, lazy;
	int l, r;
	node() {
		sum=0, lazy=-1, left=-1, right=-1;
	}
};

node st[123456*64];
int cnt=1;

void propagate(int root, int l, int r) {
	if (st[root].lazy!=-1) {
		st[root].sum=(r-l+1)*st[root].lazy;
		if (l!=r)
		{
			int mid=(l+r)/2;
			if (st[root].left==-1) {
				st[root].left = cnt++;
				st[ st[root].left ].l=l, st[ st[root].left ].r=mid;
			}
			if (st[root].right==-1) {
				st[root].right = cnt++;
				st[ st[root].right ].l=mid+1, st[ st[root].right ].r=r;
			}
			st[ st[root].left ].lazy=st[root].lazy;
			st[ st[root].right ].lazy=st[root].lazy;
		}
		st[root].lazy=-1;
	}
}

int query(int root, int left, int right, int qLeft, int qRight)
{
	propagate(root, left, right);
	if (left>qRight || right<qLeft) return 0;
	if (left>=qLeft && right<=qRight) return st[root].sum;
	int mid=(left+right)/2;
	int s1=0, s2=0;
	if (st[root].left!=-1 && mid>=qLeft) s1=query(st[root].left, left, mid, qLeft, qRight);
	if (st[root].right!=-1 && mid<qRight) s2=query(st[root].right, mid+1, right, qLeft, qRight);
	return s1+s2;
}

void update(int root, int left, int right, int qLeft, int qRight, int nValue)
{
	propagate(root, left, right);
	if (left>qRight || right<qLeft) return;
	if (left>=qLeft && right<=qRight) {
		st[root].lazy=nValue;
		propagate(root, left, right);
		return;
	}
	int mid=(left+right)/2;
	if (st[root].left==-1) {
		st[root].left = cnt++;
		st[ st[root].left ].l=left, st[ st[root].left ].r=mid;
	}
	if (st[root].right==-1) {
		st[root].right = cnt++;
		st[ st[root].right ].l=mid+1, st[ st[root].right ].r=right;
	}
	propagate(st[root].left, left, mid), propagate(st[root].right, mid+1, right);
	if (mid>=qLeft) update(st[root].left, left, mid, qLeft, qRight, nValue);
	if (mid+1<=qRight) update(st[root].right, mid+1, right, qLeft, qRight, nValue);
	st[root].sum=st[ st[root].left ].sum + st[ st[root].right ].sum;
	return;
}

int n;

void solve() {
	st[0].l=1, st[0].r=1e9;
	int q; cin >> q;
	int c=0;
	while (q--) {
		int type; cin >> type;
		int a, b; cin >> a >> b;
		a+=c, b+=c;
		if (type==1) {
			cout << (c=query(0, 1, (int)1e9, a, b)) << endl;
		} else {
			update(0, 1, (int)1e9, a, b, 1);
		}
	}
	return;
}


signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;// cin >> tt;
	while(tt--) solve();
	return 0;
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	39 ms	185940 KB	Output is correct
2	Correct	37 ms	186044 KB	Output is correct
3	Correct	36 ms	185948 KB	Output is correct
4	Correct	57 ms	186072 KB	Output is correct
5	Correct	56 ms	185952 KB	Output is correct
6	Correct	52 ms	185952 KB	Output is correct
7	Correct	61 ms	185948 KB	Output is correct
8	Correct	150 ms	186716 KB	Output is correct
9	Correct	258 ms	186264 KB	Output is correct
10	Correct	314 ms	188048 KB	Output is correct
11	Correct	292 ms	187924 KB	Output is correct
12	Correct	329 ms	188256 KB	Output is correct
13	Correct	277 ms	188496 KB	Output is correct
14	Correct	269 ms	188520 KB	Output is correct
15	Correct	329 ms	188500 KB	Output is correct
16	Correct	333 ms	188500 KB	Output is correct
17	Correct	326 ms	188472 KB	Output is correct
18	Correct	304 ms	188332 KB	Output is correct
19	Correct	329 ms	188420 KB	Output is correct
20	Correct	354 ms	188420 KB	Output is correct