oj.uz

Submission #941091

# Submission time Handle Problem Language Result Execution time Memory
941091 2024-03-08T06:48:39 Z atom Simple game (IZhO17_game) C++17
22 / 100
 18 ms 6992 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);
        // for (int i = 1; i <= n; ++i) cnt[h[i]]++;
        // for (int i = 1; i < N; ++i) cnt[i] += cnt[i - 1];
        // for (int i = 1; i <= q; ++i) {
        //     cout << cnt[queries[i][1]] << "\n";
        // }
    }
}

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 4184 KB Output is correct
3 Correct 3 ms 4444 KB Output is correct
4 Correct 4 ms 4444 KB Output is correct
5 Correct 3 ms 4444 KB Output is correct
6 Correct 4 ms 4444 KB Output is correct
7 Correct 3 ms 4444 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4184 KB Output is correct
2 Correct 3 ms 4184 KB Output is correct
3 Correct 3 ms 4444 KB Output is correct
4 Correct 4 ms 4444 KB Output is correct
5 Correct 3 ms 4444 KB Output is correct
6 Correct 4 ms 4444 KB Output is correct
7 Correct 3 ms 4444 KB Output is correct
8 Incorrect 18 ms 6992 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4184 KB Output is correct
2 Correct 3 ms 4184 KB Output is correct
3 Correct 3 ms 4444 KB Output is correct
4 Correct 4 ms 4444 KB Output is correct
5 Correct 3 ms 4444 KB Output is correct
6 Correct 4 ms 4444 KB Output is correct
7 Correct 3 ms 4444 KB Output is correct
8 Incorrect 18 ms 6992 KB Output isn't correct
9 Halted 0 ms 0 KB -