Submission #551638

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
551638	2022-04-21T08:47:07 Z	purupuddu	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	339 ms	134552 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 PersistentST
{

	using Value = int;
	using Update = bool;
	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, int _sx, int _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}};

	PersistentST(const vector<pair<ll, Value>>& data) {
		for(auto [ind, val]:data)
			update(ind, ind, val);
	}

	void push(int u, ll l, ll r) {
		if(l == r) return;
		//cout <<"l and r of pos "<<u<<" are "<<st[u].l<<' '<<st[u].r<<endl;
		if(st[u].l == -1) {
			st[u].l = ssize(st);
			//cout<<"Created st["<<u<<"].l = "<<st[u].l<<endl;
			st.push_back(Vertex(unit));
		}
		if(st[u].r == -1) {
			st[u].r = ssize(st);
			//cout<<"Created st["<<u<<"].r = "<<st[u].r<<endl;
			st.push_back(Vertex(unit));
		}
		if(st[u].upd != no_update) {
			//cout<<"CALL UPD_N ON "<<st[u].l<<endl;
			update_node(st[st[u].l], st[u].upd, l, (l+r)/2);
			//cout<<"CALL UPD_N ON "<<st[u].r<<endl;
			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) {
		//cout<<l<<' '<<r<<endl;
		if(r < x || y < l) return;
		if(x <= l && r <= y) {
			//cout<<"IM IN "<<x<<' '<<y<<' '<<l<<' '<<r<<'\n'<<u<<endl;
			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)
		{
			//cout<<"queried value "<<st[u].val<<" at pos "<<u<<" covering interval "<<l<<" - "<<r<<endl;
			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;

	PersistentST 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	1 ms	212 KB	Output is correct
3	Correct	1 ms	320 KB	Output is correct
4	Correct	12 ms	2656 KB	Output is correct
5	Correct	14 ms	2632 KB	Output is correct
6	Correct	14 ms	2660 KB	Output is correct
7	Correct	15 ms	2688 KB	Output is correct
8	Correct	107 ms	17576 KB	Output is correct
9	Correct	204 ms	34548 KB	Output is correct
10	Correct	197 ms	34356 KB	Output is correct
11	Correct	231 ms	34412 KB	Output is correct
12	Correct	201 ms	34440 KB	Output is correct
13	Correct	213 ms	68516 KB	Output is correct
14	Correct	216 ms	68540 KB	Output is correct
15	Correct	291 ms	134324 KB	Output is correct
16	Correct	322 ms	134368 KB	Output is correct
17	Correct	210 ms	68500 KB	Output is correct
18	Correct	228 ms	68624 KB	Output is correct
19	Correct	297 ms	134456 KB	Output is correct
20	Correct	339 ms	134552 KB	Output is correct