oj.uz

Submission #947367

# Submission time Handle Problem Language Result Execution time Memory
947367 2024-03-16T03:46:06 Z Pring Simple game (IZhO17_game) C++17
100 / 100
 63 ms 13164 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;

const int MXN = 1000005;
int n, q, a[MXN];

struct BIT {
    int n, val[MXN];
    void init(int _n) {
        n = _n;
        fill(val + 1, val + n + 1, 0);
    }
    void modify(int id, int v) {
        for (; id <= n; id += (id & -id)) val[id] += v;
    }
    int query(int id) {
        int ans = 0;
        for (; id > 0; id -= (id & -id)) ans += val[id];
        return ans;
    }
} B;

void ADD(int l, int r, bool inv = false) {
    if (l > r) swap(l, r);
    B.modify(l, (inv ? -1 : 1));
    B.modify(r, (inv ? 1 : -1));
}

void MODIFY(int p, int v) {
    if (p != 0) ADD(a[p - 1], a[p], true);
    if (p != n - 1) ADD(a[p], a[p + 1], true);
    a[p] = v;
    if (p != 0) ADD(a[p - 1], a[p]);
    if (p != n - 1) ADD(a[p], a[p + 1]);
}

int QUERY(int x) {
    return B.query(x);
}

void miku() {
    int t, x, y;
    cin >> n >> q;
    FOR(i, 0, n) cin >> a[i];
    B.init(1000000);
    FOR(i, 1, n) ADD(a[i - 1], a[i]);
    while (q--) {
        cin >> t;
        if (t == 1) {
            cin >> x >> y;
            MODIFY(--x, y);
        } else {
            cin >> x;
            cout << QUERY(x) << '\n';
        }
    }
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8672 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8788 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8672 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8788 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 30 ms 11860 KB Output is correct
9 Correct 34 ms 13116 KB Output is correct
10 Correct 33 ms 12940 KB Output is correct
11 Correct 33 ms 11608 KB Output is correct
12 Correct 32 ms 12892 KB Output is correct
13 Correct 34 ms 12888 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8672 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8788 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 30 ms 11860 KB Output is correct
9 Correct 34 ms 13116 KB Output is correct
10 Correct 33 ms 12940 KB Output is correct
11 Correct 33 ms 11608 KB Output is correct
12 Correct 32 ms 12892 KB Output is correct
13 Correct 34 ms 12888 KB Output is correct
14 Correct 45 ms 13056 KB Output is correct
15 Correct 49 ms 12880 KB Output is correct
16 Correct 57 ms 13164 KB Output is correct
17 Correct 63 ms 12884 KB Output is correct
18 Correct 44 ms 12868 KB Output is correct