oj.uz

Submission #332206

# Submission time Handle Problem Language Result Execution time Memory
332206 2020-12-01T16:44:48 Z vitkishloh228 Simple game (IZhO17_game) C++14
100 / 100
 561 ms 19584 KB 
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 1000004;
int t[4 * N], mod[4 * N];
void push(int v, int l, int r) {
    if (l == r) {
        mod[v] = 0;
        return;
    }
    mod[2 * v] += mod[v];
    mod[2 * v + 1] += mod[v];
    t[2 * v] += mod[v];
    t[2 * v + 1] += mod[v];
    mod[v] = 0;
    return;
}
void upd(int v, int tl, int tr, int l, int r, int x) {
    push(v, tl, tr);
    if (tl > tr || l > r) return;
    if (tl == l && tr == r) {
        mod[v] += x;
        t[v] += x;
        return;
    }
    int tm = (tl + tr) >> 1;
    upd(2 * v, tl, tm, l, min(r, tm), x);
    upd(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, x);
}
int getelem(int v, int tl, int tr, int pos) {
    push(v, tl, tr);
    if (tl == tr) {
        return t[v];
    }
    int tm = (tl + tr) >> 1;
    if (pos <= tm) {
        return getelem(2 * v, tl, tm, pos);
    }
    return getelem(2 * v + 1, tm + 1, tr, pos);
}
int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n - 1; ++i) {
        upd(1, 0, N - 1, min(a[i], a[i + 1]), max(a[i], a[i + 1]), 1);
    }
    while (q--) {
        int type;
        cin >> type;
        if (type == 2) {
            int H;
            cin >> H;
            cout << getelem(1, 0, N - 1, H) << '\n';
        }
        else {
            int pos, val;
            cin >> pos >> val;
            --pos;
            if (pos) {
                upd(1, 0, N - 1, min(a[pos - 1], a[pos]), max(a[pos - 1], a[pos]), -1);
            }
            if (pos + 1 < n) {
                upd(1, 0, N - 1, min(a[pos + 1], a[pos]), max(a[pos + 1], a[pos]), -1);
            }
            a[pos] = val;
            if (pos) {
                upd(1, 0, N - 1, min(a[pos - 1], a[pos]), max(a[pos - 1], a[pos]), 1);
            }
            if (pos + 1 < n) {
                upd(1, 0, N - 1, min(a[pos + 1], a[pos]), max(a[pos + 1], a[pos]), 1);
            }
        }
    }
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 14 ms 15212 KB Output is correct
3 Correct 16 ms 15084 KB Output is correct
4 Correct 18 ms 15212 KB Output is correct
5 Correct 14 ms 15212 KB Output is correct
6 Correct 14 ms 15084 KB Output is correct
7 Correct 11 ms 12780 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 14 ms 15212 KB Output is correct
3 Correct 16 ms 15084 KB Output is correct
4 Correct 18 ms 15212 KB Output is correct
5 Correct 14 ms 15212 KB Output is correct
6 Correct 14 ms 15084 KB Output is correct
7 Correct 11 ms 12780 KB Output is correct
8 Correct 335 ms 1900 KB Output is correct
9 Correct 479 ms 19584 KB Output is correct
10 Correct 487 ms 19436 KB Output is correct
11 Correct 327 ms 1772 KB Output is correct
12 Correct 378 ms 3436 KB Output is correct
13 Correct 425 ms 19308 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 14 ms 15212 KB Output is correct
3 Correct 16 ms 15084 KB Output is correct
4 Correct 18 ms 15212 KB Output is correct
5 Correct 14 ms 15212 KB Output is correct
6 Correct 14 ms 15084 KB Output is correct
7 Correct 11 ms 12780 KB Output is correct
8 Correct 335 ms 1900 KB Output is correct
9 Correct 479 ms 19584 KB Output is correct
10 Correct 487 ms 19436 KB Output is correct
11 Correct 327 ms 1772 KB Output is correct
12 Correct 378 ms 3436 KB Output is correct
13 Correct 425 ms 19308 KB Output is correct
14 Correct 561 ms 19564 KB Output is correct
15 Correct 559 ms 19308 KB Output is correct
16 Correct 548 ms 19308 KB Output is correct
17 Correct 548 ms 19436 KB Output is correct
18 Correct 550 ms 19460 KB Output is correct