제출 #1257337

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257337		proofy	Simple game (IZhO17_game)	C++20	0 / 100	3 ms	6468 KiB

game

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 1000123;
int fenw[N];

void add(int i, int v) {
    for (++i; i < N; i += (i & -i)) fenw[i] += v;
}
int query(int i) {
    int res = 0;
    for (++i; i > 0; i -= (i & -i)) res += fenw[i];
    return res;
}

void add_range(int l, int r, int v) {
    add(l, v);
    add(r + 1, -v);
}

int h[N];

void add_contribution(int x, int y) {
    if (x > y) swap(x, y);
    add_range(x, y, 1);
}
void remove_contribution(int x, int y) {
    if (x > y) swap(x, y);
    add_range(x, y, -1);
}


int32_t main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> h[i];

    for (int i = 1; i <= n; i++) {
      add_contribution(h[i], h[i + 1]);
    }


    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int i, v;
            cin >> i >> v;
            if (i > 1) remove_contribution(h[i - 1], h[i]);
            if (i + 1 <= n) remove_contribution(h[i + 1], h[i]);

            h[i] = v;

            if (i > 1) add_contribution(h[i - 1], h[i]);
            if (i + 1 <= n) add_contribution(h[i + 1], h[i]);
        } else {
            int x;
            cin >> x;

            cout << query(x) << "\n";
        }
    }
}

• Subtask 1: 0 / 22
• Subtask 2: 0 / 27
• Subtask 3: 0 / 51