답안 #915832

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
915832	2024-01-24T18:46:42 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[100000*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	150624 KB	Output is correct
2	Correct	31 ms	150532 KB	Output is correct
3	Correct	33 ms	150672 KB	Output is correct
4	Correct	43 ms	150608 KB	Output is correct
5	Correct	45 ms	150584 KB	Output is correct
6	Correct	45 ms	150760 KB	Output is correct
7	Correct	45 ms	150736 KB	Output is correct
8	Correct	147 ms	150868 KB	Output is correct
9	Correct	308 ms	151104 KB	Output is correct
10	Correct	314 ms	151112 KB	Output is correct
11	Correct	333 ms	151156 KB	Output is correct
12	Correct	294 ms	151044 KB	Output is correct
13	Correct	265 ms	151060 KB	Output is correct
14	Correct	260 ms	151124 KB	Output is correct
15	Execution timed out	2649 ms	262144 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-