Submission #551645

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
551645	2022-04-21T09:03:58 Z	purupuddu	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	431 ms	197932 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 = 1.1e9;
	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	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	14 ms	3576 KB	Output is correct
5	Correct	15 ms	3476 KB	Output is correct
6	Correct	17 ms	3564 KB	Output is correct
7	Correct	15 ms	3492 KB	Output is correct
8	Correct	106 ms	25096 KB	Output is correct
9	Correct	228 ms	49792 KB	Output is correct
10	Correct	235 ms	49828 KB	Output is correct
11	Correct	247 ms	49868 KB	Output is correct
12	Correct	243 ms	49792 KB	Output is correct
13	Correct	239 ms	99344 KB	Output is correct
14	Correct	239 ms	99508 KB	Output is correct
15	Correct	411 ms	197932 KB	Output is correct
16	Correct	395 ms	197868 KB	Output is correct
17	Correct	270 ms	99276 KB	Output is correct
18	Correct	279 ms	99256 KB	Output is correct
19	Correct	431 ms	197852 KB	Output is correct
20	Correct	399 ms	197888 KB	Output is correct