Submission #915819

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
915819	2024-01-24T18:27:56 Z	Nonoze	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	311 ms	132760 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;
	}
};

vector<node> st(100000*56);
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=5e8;
	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)5e8, a, b)) << endl;
		} else {
			update(0, 1, (int)5e8, 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	28 ms	131920 KB	Output is correct
2	Correct	28 ms	131732 KB	Output is correct
3	Correct	27 ms	131932 KB	Output is correct
4	Correct	40 ms	131920 KB	Output is correct
5	Correct	45 ms	131932 KB	Output is correct
6	Correct	42 ms	131932 KB	Output is correct
7	Correct	44 ms	131928 KB	Output is correct
8	Correct	128 ms	132004 KB	Output is correct
9	Correct	270 ms	132760 KB	Output is correct
10	Correct	305 ms	132176 KB	Output is correct
11	Correct	278 ms	132176 KB	Output is correct
12	Correct	311 ms	132244 KB	Output is correct
13	Incorrect	182 ms	132436 KB	Output isn't correct
14	Halted	0 ms	0 KB	-