oj.uz

Submission #849219

# Submission time Handle Problem Language Result Execution time Memory
849219 2023-09-14T09:27:48 Z wakandaaa Simple game (IZhO17_game) C++17
100 / 100
 43 ms 9268 KB 
#include <bits/stdc++.h>

using namespace std;

#define file ""

#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()

#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1LL << (x))
#define popcount __builtin_popcountll

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
    return l + rd() % (r - l + 1);
}

const int N = 1e6 + 5;
const int mod = (int)1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int oo = 1e9;
const long long ooo = 1e18;

template<class X, class Y> bool mini(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maxi(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}
void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

int n, q;
int h[N];
int bit[N];

void update(int u, int c) {
    for (; u < N; u += u & (-u)) bit[u] += c;
}
int get(int u) {
    int res = 0;
    for (; u > 0; u -= u & (-u)) res += bit[u];
    return res;
}
int get(int l, int r) {
    return get(r) - get(l - 1);
}
void update(int l, int r, int c) {
    update(l, c);
    update(r + 1, -c);
}

void add(int i) {
    if (i < 1 || i >= n) return;
    int l = min(h[i], h[i + 1]);
    int r = max(h[i], h[i + 1]);
    update(l, r, 1);
}
void del(int i) {
    if (i < 1 || i >= n) return;
    int l = min(h[i], h[i + 1]);
    int r = max(h[i], h[i + 1]);
    update(l, r, -1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);

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

    for (int i = 1; i <= n; ++i)
        add(i);

    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int pos, newH;
            cin >> pos >> newH;
            del(pos - 1);
            del(pos);
            h[pos] = newH;
            add(pos - 1);
            add(pos);
        }
        else {
            int x;
            cin >> x;
            cout << get(x) << '\n';
        }
    }

    return 0;
}

/*

*/

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 1 ms 4696 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 2 ms 4696 KB Output is correct
6 Correct 2 ms 4760 KB Output is correct
7 Correct 1 ms 4644 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 1 ms 4696 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 2 ms 4696 KB Output is correct
6 Correct 2 ms 4760 KB Output is correct
7 Correct 1 ms 4644 KB Output is correct
8 Correct 31 ms 7504 KB Output is correct
9 Correct 34 ms 8784 KB Output is correct
10 Correct 38 ms 9268 KB Output is correct
11 Correct 29 ms 7260 KB Output is correct
12 Correct 37 ms 8532 KB Output is correct
13 Correct 29 ms 8536 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 1 ms 4696 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 2 ms 4696 KB Output is correct
6 Correct 2 ms 4760 KB Output is correct
7 Correct 1 ms 4644 KB Output is correct
8 Correct 31 ms 7504 KB Output is correct
9 Correct 34 ms 8784 KB Output is correct
10 Correct 38 ms 9268 KB Output is correct
11 Correct 29 ms 7260 KB Output is correct
12 Correct 37 ms 8532 KB Output is correct
13 Correct 29 ms 8536 KB Output is correct
14 Correct 41 ms 8784 KB Output is correct
15 Correct 42 ms 8784 KB Output is correct
16 Correct 43 ms 9040 KB Output is correct
17 Correct 42 ms 8784 KB Output is correct
18 Correct 43 ms 8776 KB Output is correct