Submission #624913

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
624913	2022-08-09T04:16:59 Z	DeMen100ns	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	451 ms	200088 KB

apple

//icant

#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	320 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	15 ms	3656 KB	Output is correct
5	Correct	17 ms	3656 KB	Output is correct
6	Correct	18 ms	3648 KB	Output is correct
7	Correct	17 ms	3680 KB	Output is correct
8	Correct	118 ms	25940 KB	Output is correct
9	Correct	277 ms	51076 KB	Output is correct
10	Correct	286 ms	50800 KB	Output is correct
11	Correct	269 ms	50868 KB	Output is correct
12	Correct	276 ms	50848 KB	Output is correct
13	Correct	267 ms	101340 KB	Output is correct
14	Correct	297 ms	101560 KB	Output is correct
15	Correct	419 ms	200088 KB	Output is correct
16	Correct	451 ms	199980 KB	Output is correct
17	Correct	310 ms	101400 KB	Output is correct
18	Correct	272 ms	101388 KB	Output is correct
19	Correct	399 ms	200036 KB	Output is correct
20	Correct	423 ms	200040 KB	Output is correct