oj.uz

Submission #759799

# Submission time Handle Problem Language Result Execution time Memory
759799 2023-06-16T19:46:44 Z NK_ Simple game (IZhO17_game) C++17
100 / 100
 298 ms 19348 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

struct Seg {
	const int ID = 0; int comb(int a, int b) { return a + b; }
	vector<int> seg, lazy; int N; 

	void init(int _N) {
		N = 1; while(N < _N) N *= 2;
		seg.assign(2*N, ID); lazy.assign(2*N, ID);
	}

	void pull(int x) { seg[x] = comb(seg[2*x], seg[2*x+1]); }

	void push(int x, int L, int R) {
		seg[x] += (R - L + 1) * lazy[x];
		if (L != R) for(int i = 0; i < 2; i++) lazy[2*x+i] += lazy[x];
		lazy[x] = 0;
	}

	void upd(int l, int r, int v, int x = 1, int L = 0, int R = -1) {
		if (R == -1) R = N - 1;
		push(x, L, R);
		if (r < L || R < l) return;
		if (l <= L && R <= r) {
			lazy[x] = v; push(x, L, R); return;
		}

		int M = (L + R) / 2;
		upd(l, r, v, 2 * x, L, M); upd(l, r, v, 2 * x + 1, M + 1, R);
		pull(x);
	};

	int query(int l, int r, int x = 1, int L = 0, int R = -1) {
		if (R == -1) R = N - 1;
		push(x, L, R);
		if (r < L || R < l) return ID;
		if (l <= L && R <= r) return seg[x];

		int M = (L + R) / 2;
		return comb(query(l, r, 2 * x, L, M), query(l, r, 2 * x + 1, M + 1, R));
	};
};


const int MX = (1 << 20);
int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, Q; cin >> N >> Q;
	vector<int> A(N); for(auto& x : A) cin >> x;

	Seg st; st.init(MX);

	auto upd = [&](int i, int d) {
		int l = min(A[i], A[i+1]), r = max(A[i], A[i+1]);
		st.upd(l, r, d);
	};	

	for(int i = 0; i < N-1; i++) upd(i, 1);

	for(int q = 0; q < Q; q++) {
		int t; cin >> t;
		if (t == 1) {
			int i, x; cin >> i >> x; --i;
			if (i-1 >= 0) upd(i-1, -1);
			if (i+1 < N) upd(i, -1);

			A[i] = x;

			if (i-1 >= 0) upd(i-1, +1);
			if (i+1 < N) upd(i, +1);
		} else {
			int h; cin >> h;
			cout << st.query(h, h) << nl;
		}
	}


    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 11 ms 16688 KB Output is correct
3 Correct 11 ms 16740 KB Output is correct
4 Correct 11 ms 16724 KB Output is correct
5 Correct 11 ms 16724 KB Output is correct
6 Correct 11 ms 16712 KB Output is correct
7 Correct 9 ms 16720 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 11 ms 16688 KB Output is correct
3 Correct 11 ms 16740 KB Output is correct
4 Correct 11 ms 16724 KB Output is correct
5 Correct 11 ms 16724 KB Output is correct
6 Correct 11 ms 16712 KB Output is correct
7 Correct 9 ms 16720 KB Output is correct
8 Correct 78 ms 18008 KB Output is correct
9 Correct 162 ms 19288 KB Output is correct
10 Correct 146 ms 19348 KB Output is correct
11 Correct 75 ms 17996 KB Output is correct
12 Correct 111 ms 19036 KB Output is correct
13 Correct 146 ms 19092 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 11 ms 16688 KB Output is correct
3 Correct 11 ms 16740 KB Output is correct
4 Correct 11 ms 16724 KB Output is correct
5 Correct 11 ms 16724 KB Output is correct
6 Correct 11 ms 16712 KB Output is correct
7 Correct 9 ms 16720 KB Output is correct
8 Correct 78 ms 18008 KB Output is correct
9 Correct 162 ms 19288 KB Output is correct
10 Correct 146 ms 19348 KB Output is correct
11 Correct 75 ms 17996 KB Output is correct
12 Correct 111 ms 19036 KB Output is correct
13 Correct 146 ms 19092 KB Output is correct
14 Correct 265 ms 19304 KB Output is correct
15 Correct 282 ms 19304 KB Output is correct
16 Correct 298 ms 19256 KB Output is correct
17 Correct 274 ms 19240 KB Output is correct
18 Correct 281 ms 19276 KB Output is correct