oj.uz

Submission #941098

# Submission time Handle Problem Language Result Execution time Memory
941098 2024-03-08T07:05:23 Z atom Simple game (IZhO17_game) C++17
49 / 100
 45 ms 16208 KB 
#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;

#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif

struct Fenwick {
    int n;
    vector <int> f;
    
    Fenwick (int _n): n(_n), f(_n + 5) {};
    int qry(int x) {
        int ans = 0;
        for (; x; x -= x & -x)
            ans += f[x];
        return ans;
    }
    void add(int x, int val) {
        for (; x <= n; x += x & -x)
            f[x] += val;
    }
};

const int N = 1e6 + 5;
signed main() {
    cin.tie(0) -> sync_with_stdio(0);

    int n, q;
    cin >> n >> q;
    vector <int> h(n + 5);
    vector <vector <int>> queries(q + 5);

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

    bool sub2 = 1;
    for (int i = 1; i <= q; ++i) {
        int cmd; cin >> cmd;
        if (cmd == 1) {
            int x, y; cin >> x >> y;
            queries[i] = {cmd, x, y};
            sub2 = 0;
        }
        else {
            int x; cin >> x;
            queries[i] = {cmd, x};
        }
    }

    // sub1
    if (n <= 1000 && q <= 1000) {
        vector <int> cnt(N, 0);
        for (int i = 1; i <= n; ++i) cnt[h[i]]++;
        for (int i = 1; i <= q; ++i) {
            if (queries[i][0] == 1) {
                cnt[h[queries[i][1]]]--;
                h[queries[i][1]] = queries[i][2];
                cnt[h[queries[i][1]]]++;
            }
            else {
                int ans = 0;
                int H = queries[i][1];
                for (int j = 2; j <= n; ++j)
                    if ((h[j - 1] < H && H < h[j]) || (h[j - 1] > H && H > h[j]))
                        ++ans;
                cout << ans << "\n";
            }
        }
    }
    else if (sub2) {
        // Fenwick
        vector <int> cnt(N);
        vector <int> prf(N);
        for (int i = 1; i <= n; ++i)
            cnt[h[i]]++;
        for (int i = 2; i <= n; ++i) {
            int l = h[i - 1], r = h[i];
            if (l > r) swap(l, r);
            l++, r--;
            if (l <= r) {
                prf[l]++;
                prf[r + 1]--;
            }
        }
        for (int i = 1; i < N; ++i) prf[i] += prf[i - 1];
        for (int i = 1; i <= q; ++i) {
            cout << (cnt[queries[i][1]] + prf[queries[i][1]]) << "\n";
        }
    }
    else {

    }
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4184 KB Output is correct
2 Correct 3 ms 4444 KB Output is correct
3 Correct 3 ms 4184 KB Output is correct
4 Correct 3 ms 4444 KB Output is correct
5 Correct 3 ms 4444 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 2 ms 4188 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4184 KB Output is correct
2 Correct 3 ms 4444 KB Output is correct
3 Correct 3 ms 4184 KB Output is correct
4 Correct 3 ms 4444 KB Output is correct
5 Correct 3 ms 4444 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 2 ms 4188 KB Output is correct
8 Correct 30 ms 14172 KB Output is correct
9 Correct 45 ms 16208 KB Output is correct
10 Correct 35 ms 16208 KB Output is correct
11 Correct 27 ms 14936 KB Output is correct
12 Correct 31 ms 15952 KB Output is correct
13 Correct 32 ms 16132 KB Output is correct

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4184 KB Output is correct
2 Correct 3 ms 4444 KB Output is correct
3 Correct 3 ms 4184 KB Output is correct
4 Correct 3 ms 4444 KB Output is correct
5 Correct 3 ms 4444 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 2 ms 4188 KB Output is correct
8 Correct 30 ms 14172 KB Output is correct
9 Correct 45 ms 16208 KB Output is correct
10 Correct 35 ms 16208 KB Output is correct
11 Correct 27 ms 14936 KB Output is correct
12 Correct 31 ms 15952 KB Output is correct
13 Correct 32 ms 16132 KB Output is correct
14 Incorrect 25 ms 8016 KB Output isn't correct
15 Halted 0 ms 0 KB -