oj.uz

Submission #673248

# Submission time Handle Problem Language Result Execution time Memory
673248 2022-12-20T03:18:18 Z moday_morning Simple game (IZhO17_game) C++17
100 / 100
 168 ms 19744 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1'000'002;
const int H = 1'000'000;
int a[N], t[4 * N];
void update (int v, int vl, int vr, int l, int r, int val) {
    if (vl == l && r == vr)
    {
        t[v] += val;
        return;
    }
    int m = (vl + vr) / 2;
    if (l <= m)
        update (v * 2, vl, m, l, min (r, m), val);
    if (r > m)
        update (v * 2 + 1, m + 1, vr, max (m + 1, l), r, val);
}

int coutt (int v, int vl, int vr, int pos) {
    if (vl == vr)
        return t[v];
    int m = (vl + vr) / 2;
    if (pos <= m)
        return t[v] + coutt (v * 2, vl, m, pos);
    return t[v] + coutt (v * 2 + 1, m + 1, vr, pos);
}

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (i != 0) {
            update (1, 1, H, min (a[i - 1], a[i]), max (a[i - 1], a[i]), 1);
        }
    }
    while (m--) {
        int type;
        cin >> type;
        if (type == 1) {
            int pos, val;
            cin >> pos >> val;
            pos--;
            if (pos != 0) {
                update (1, 1, H, min (a[pos - 1], a[pos]), max (a[pos - 1], a[pos]), -1);
                update (1, 1, H, min (a[pos - 1], val), max (a[pos - 1], val), 1);
            }
            if (pos != n - 1) {
                update (1, 1, H, min (a[pos + 1], a[pos]), max (a[pos + 1], a[pos]), -1);
                update (1, 1, H, min (a[pos + 1], val), max (a[pos + 1], val), 1);
            }
            a[pos] = val;
        }
        else {
            int h;
            cin >> h;
            cout << coutt (1, 1, H, h) << '\n';
        }
    }
}

signed main() {
//    usaco("A");
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9300 KB Output is correct
4 Correct 9 ms 9296 KB Output is correct
5 Correct 6 ms 9428 KB Output is correct
6 Correct 6 ms 9560 KB Output is correct
7 Correct 2 ms 340 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9300 KB Output is correct
4 Correct 9 ms 9296 KB Output is correct
5 Correct 6 ms 9428 KB Output is correct
6 Correct 6 ms 9560 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 35 ms 2040 KB Output is correct
9 Correct 93 ms 19744 KB Output is correct
10 Correct 94 ms 19740 KB Output is correct
11 Correct 38 ms 1996 KB Output is correct
12 Correct 59 ms 3528 KB Output is correct
13 Correct 39 ms 3128 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9300 KB Output is correct
4 Correct 9 ms 9296 KB Output is correct
5 Correct 6 ms 9428 KB Output is correct
6 Correct 6 ms 9560 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 35 ms 2040 KB Output is correct
9 Correct 93 ms 19744 KB Output is correct
10 Correct 94 ms 19740 KB Output is correct
11 Correct 38 ms 1996 KB Output is correct
12 Correct 59 ms 3528 KB Output is correct
13 Correct 39 ms 3128 KB Output is correct
14 Correct 163 ms 19728 KB Output is correct
15 Correct 160 ms 19728 KB Output is correct
16 Correct 168 ms 19740 KB Output is correct
17 Correct 166 ms 19652 KB Output is correct
18 Correct 168 ms 19612 KB Output is correct