Submission #344419

#	Time	Username	Problem	Language	Result	Execution time	Memory
344419		apostoldaniel854	Simple game (IZhO17_game)	C++14	100 / 100	77 ms	6508 KiB

game

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"

const int MAX_N = 1e5, MX = 1e6;
int aib[1 + MX];
int h[1 + MAX_N];


void update (int pos, int val) {
    while (pos <= MX) {
        aib[pos] += val;
        pos += pos & -pos;
    }
}
int query (int pos) {
    int ans = 0;
    while (pos > 0) {
        ans += aib[pos];
        pos -= pos & -pos;
    }
    return ans;
}

void change (int l, int r, int sgn) {
    if (l > r)
        swap (l, r);
    update (l, sgn);
    update (r + 1, -sgn);
}

int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> h[i];
    for (int i = 2; i <= n; i++)
        change (h[i - 1], h[i], 1);
    while (m--) {
        int type;
        cin >> type;
        if (type == 1) {
            int pos, new_h;
            cin >> pos >> new_h;
            if (pos > 1)
                change (h[pos - 1], h[pos], -1);
            if (pos < n)
                change (h[pos], h[pos + 1], -1);
            h[pos] = new_h;
            if (pos > 1)
                change (h[pos - 1], h[pos], 1);
            if (pos < n)
                change (h[pos], h[pos + 1], 1);
        }
        else {
            int h;
            cin >> h;
            cout << query (h) << "\n";
        }
    }
    return 0;
}
/**
3 3
1 5 1
2 3
1 1 5
2 3
**/

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