Submission #551666

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
551666	2022-04-21T09:34:23 Z	purupuddu	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	504 ms	197888 KB

apple

#include<bits/stdc++.h>
using namespace std;

#define all(c) begin(c), end(c)
#define rep(ind, st, end) for(int ind = st;ind<end; ind++)
#define ssize(c) static_cast<int>(c.size())
#define pb push_back
#define F first
#define S second
#define endl '\n'
#define vv vector<vector

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<ll>>;
using pll = pair<ll, ll>;
using vvpii = vector<vector<pii>>;



struct SparseST
{

	using Value = ll;
	using Update = ll;
	ll inf = LLONG_MAX;
	Value unit = Value(0);
	static const Update no_update = Update{0}; // null update

	Value merge(Value a, Value b) { return a + b; }

	struct Vertex {
		Value val;
		int l = -1, r = -1;
		Update upd = no_update;
		Vertex(Value v, ll _sx, ll _dx) : val(v), l(_sx), r(_dx) {}
		Vertex(Value v) : val(v) {}
	};


	void update_node(Vertex& a, Update upd, ll l, ll r) {
		a.val = upd * (r - l + 1);
	}
	Update combine_updates(Update prev, Update upd) {
		return upd;
	}

	vector<Vertex> st{Vertex{unit}};


	void push(int u, ll l, ll r) {
		if(l == r) return;
		if(st[u].l == -1) {
			st[u].l = ssize(st);
			st.push_back(Vertex(unit));
		}
		if(st[u].r == -1) {
			st[u].r = ssize(st);
			st.push_back(Vertex(unit));
		}
		if(st[u].upd != no_update) {
			update_node(st[st[u].l], st[u].upd, l, (l+r)/2);
			update_node(st[st[u].r], st[u].upd, (l+r)/2+1, r);
			if(l < r) {
				st[st[u].l].upd = combine_updates(st[st[u].l].upd, st[u].upd);
				st[st[u].r].upd = combine_updates(st[st[u].r].upd, st[u].upd);
			}
			st[u].upd = no_update;
		}
	}

	void update(int u, ll l, ll r, ll x, ll y, Update v) {
		if(r < x || y < l) return;
		if(x <= l && r <= y) {
			update_node(st[u], v, l, r);
			if(l != r)
				st[u].upd = combine_updates(st[u].upd, v);
		}
		else {
			push(u, l, r);
			update(st[u].l, l, (l+r)/2, x, y, v);
			update(st[u].r, (l+r)/2+1, r, x, y, v);
			st[u].val = merge(st[st[u].l].val, st[st[u].r].val);
		}
	}

	Value query(int u, ll l, ll r, ll x, ll y) {
		//cout<<"sto a "<<l <<' '<<r<<' '<<st[u].val<<' '<<st[u].upd<<" dpt = "<<dpt<<endl;
		if(r < x || l > y) return unit;
		if(l >= x && r <= y)
		{
			return st[u].val;
		}
		push(u, l, r);
		return merge(
			query(st[u].l, l, (l+r)/2, x, y),
			query(st[u].r, (l+r)/2+1, r, x, y)
		);
	}

	// [x, y]
	Value query(ll x, ll y) { return query(0, 0, inf, x, y); }
	void update(ll x, ll y, Update v) { update(0, 0, inf, x, y, v); }

};





int main() {
	iostream::sync_with_stdio(false);
	cin.tie(0);
	int m;
	cin >> m;

	SparseST st;

	int c = 0;
	rep(i, 0, m) {
		int d, x, y;
		cin >> d >> x >> y;
		if (d == 1) {
			c = st.query(x + c, y + c);
			cout << c << '\n';
		} else st.update(x + c, y + c, 1);
	}
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	17 ms	3540 KB	Output is correct
5	Correct	20 ms	3512 KB	Output is correct
6	Correct	20 ms	3452 KB	Output is correct
7	Correct	23 ms	3528 KB	Output is correct
8	Correct	143 ms	25124 KB	Output is correct
9	Correct	294 ms	49900 KB	Output is correct
10	Correct	298 ms	49816 KB	Output is correct
11	Correct	329 ms	49836 KB	Output is correct
12	Correct	360 ms	49824 KB	Output is correct
13	Correct	330 ms	99356 KB	Output is correct
14	Correct	327 ms	99268 KB	Output is correct
15	Correct	476 ms	197888 KB	Output is correct
16	Correct	504 ms	197840 KB	Output is correct
17	Correct	350 ms	99272 KB	Output is correct
18	Correct	306 ms	99348 KB	Output is correct
19	Correct	453 ms	197836 KB	Output is correct
20	Correct	412 ms	197840 KB	Output is correct