oj.uz

답안 #624913

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
624913 2022-08-09T04:16:59 Z DeMen100ns 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
 451 ms 200088 KB 
//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

# 결과 실행 시간 메모리 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