답안 #915833

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
915833	2024-01-24T18:47:18 Z	Nonoze	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	2000 ms	262144 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[100005*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

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	150620 KB	Output is correct
2	Correct	31 ms	150620 KB	Output is correct
3	Correct	31 ms	150620 KB	Output is correct
4	Correct	42 ms	150780 KB	Output is correct
5	Correct	46 ms	150612 KB	Output is correct
6	Correct	46 ms	150620 KB	Output is correct
7	Correct	46 ms	150576 KB	Output is correct
8	Correct	129 ms	150772 KB	Output is correct
9	Correct	272 ms	151020 KB	Output is correct
10	Correct	298 ms	151036 KB	Output is correct
11	Correct	272 ms	151124 KB	Output is correct
12	Correct	262 ms	150996 KB	Output is correct
13	Correct	247 ms	151108 KB	Output is correct
14	Correct	246 ms	151052 KB	Output is correct
15	Execution timed out	2686 ms	262144 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-