Submission #1025845

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025845		phoenix	Simple game (IZhO17_game)	C++17	100 / 100	186 ms	19656 KiB

game

#include <bits/stdc++.h>

using namespace std;

const int N = 100100;
const int M = 200200;

struct FenwickTree {
    int st[M] = {};

    void update(int pos, int val) {
        for (; pos < M; pos += (pos & -pos))
            st[pos] += val;
    }

    int get(int pos) {
        int res = 0;
        for (; pos; pos -= (pos & -pos))
            res += st[pos];
        return res;
    }
};

FenwickTree Ox, Oy, XY;

int n, m;
int h[N];
vector<vector<int>> queries;

int main() {
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    #endif

    // ios::sync_with_stdio(0);
    // cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }
    for (int i = 0; i < m; i++) {
        int tp;
        cin >> tp;
        if (tp == 1) {
            int pos, val;
            cin >> pos >> val;
            pos--;
            queries.push_back({tp, pos, val});
        } else {
            int H;
            cin >> H;   
            queries.push_back({tp, H});
        }
    }
    
    /* COMPRESS */ {
        map<int, int> mp;
        for (int i = 0; i < n; i++)
            mp[h[i]] = 1;
        for (int i = 0; i < m; i++) {
            mp[queries[i].back()] = 1;
        }
        int k = 1;
        for (auto &c : mp) 
            c.second = k++;
        for (int i = 0; i < n; i++)
            h[i] = mp[h[i]];
        for (int i = 0; i < m; i++)
            queries[i].back() = mp[queries[i].back()];       
    }

    for (int i = 0; i < n - 1; i++) {
        int x = h[i], y = h[i + 1];
        Ox.update(x, +1);
        Oy.update(y, +1);
        XY.update(max(x, y), +1);
    }

    for (int i = 0; i < m; i++) {
        int t = queries[i][0];
        if (t == 1) {
            int pos = queries[i][1], val = queries[i][2];
            if (pos) {
                Ox.update(h[pos - 1], -1);
                Oy.update(h[pos], -1);
                XY.update(max(h[pos - 1], h[pos]), -1);
            }
            if (pos < n - 1) {
                Ox.update(h[pos], -1);
                Oy.update(h[pos + 1], -1);
                XY.update(max(h[pos], h[pos + 1]), -1);
            }
            h[pos] = val;
            if (pos) {
                Ox.update(h[pos - 1], +1);
                Oy.update(h[pos], +1);
                XY.update(max(h[pos - 1], h[pos]), +1);
            }
            if (pos < n - 1) {
                Ox.update(h[pos], +1);
                Oy.update(h[pos + 1], +1);
                XY.update(max(h[pos], h[pos + 1]), +1);
            }
        } else {
            int H = queries[i][1];
            int ans = Ox.get(H) + Oy.get(H) - 2 * XY.get(H);
            cout << ans << '\n';
        }
    }

    return 0;
}

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