oj.uz

Submission #1025845

# Submission time Handle Problem Language Result Execution time Memory
1025845 2024-07-17T10:45:08 Z phoenix Simple game (IZhO17_game) C++17
100 / 100
 186 ms 19656 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 58 ms 8456 KB Output is correct
9 Correct 177 ms 17916 KB Output is correct
10 Correct 172 ms 19656 KB Output is correct
11 Correct 48 ms 9476 KB Output is correct
12 Correct 120 ms 11516 KB Output is correct
13 Correct 107 ms 14648 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 58 ms 8456 KB Output is correct
9 Correct 177 ms 17916 KB Output is correct
10 Correct 172 ms 19656 KB Output is correct
11 Correct 48 ms 9476 KB Output is correct
12 Correct 120 ms 11516 KB Output is correct
13 Correct 107 ms 14648 KB Output is correct
14 Correct 182 ms 19376 KB Output is correct
15 Correct 176 ms 19496 KB Output is correct
16 Correct 184 ms 19492 KB Output is correct
17 Correct 186 ms 19448 KB Output is correct
18 Correct 183 ms 19452 KB Output is correct