Submission #915825

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
915825	2024-01-24T18:40:54 Z	Nonoze	Monkey and Apple-trees (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[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) s1=query(st[root].left, left, mid, qLeft, qRight);
	if (st[root].right!=-1) 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

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	185932 KB	Output is correct
2	Correct	37 ms	185936 KB	Output is correct
3	Correct	36 ms	185744 KB	Output is correct
4	Correct	50 ms	185936 KB	Output is correct
5	Correct	52 ms	186008 KB	Output is correct
6	Correct	56 ms	186080 KB	Output is correct
7	Correct	58 ms	186004 KB	Output is correct
8	Correct	141 ms	185988 KB	Output is correct
9	Correct	307 ms	186124 KB	Output is correct
10	Correct	289 ms	186544 KB	Output is correct
11	Correct	304 ms	186224 KB	Output is correct
12	Correct	311 ms	186588 KB	Output is correct
13	Correct	256 ms	186316 KB	Output is correct
14	Correct	254 ms	186452 KB	Output is correct
15	Execution timed out	2578 ms	262144 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-