제출 #759799

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
759799		NK_	Simple game (IZhO17_game)	C++17	100 / 100	298 ms	19348 KiB

game

// 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 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51