oj.uz

Submission #171562

# Submission time Handle Problem Language Result Execution time Memory
171562 2019-12-29T08:29:08 Z mcdx9524 Simple game (IZhO17_game) C++14
100 / 100
 526 ms 35832 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6;

ll t[4 * N];
ll lz[4 * N];

void push(int v, int tl, int tr) {
    if (!lz[v]) {
        return;
    }
    t[v] += lz[v] * (tr - tl + 1);
    if (tl != tr) {
        lz[2 * v + 1] += lz[v];
        lz[2 * v + 2] += lz[v];
    }
    lz[v] = 0;
}

void upd(int v, int tl, int tr, int l, int r, int x) {
    push(v, tl, tr);
    if (l > tr || r < tl) {
        return;
    } else if (l <= tl && tr <= r) {
        lz[v] += x;
        push(v, tl, tr);
        return;
    } else {
        int tm = (tl + tr) / 2;
        upd(2 * v + 1, tl, tm, l, r, x);
        upd(2 * v + 2, tm + 1, tr, l, r, x);
        t[v] = t[2 * v + 1] + t[2 * v + 2];
    }
}

ll get(int v, int tl, int tr, int l, int r) {
    push(v, tl, tr);
    if (l > tr || r < tl) {
        return 0;
    } else if (l <= tl && tr <= r) {
        return t[v];
    } else {
        int tm = (tl + tr) / 2;
        return get(2 * v + 1, tl, tm, l, r) + get(2 * v + 2, tm + 1, tr, l, r);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector <int> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }
    for (int i = 1; i < n; i++) {
        upd(0, 0, N - 1, min(h[i], h[i - 1]), max(h[i], h[i - 1]), 1);
    }
    for (int it = 0; it < m; it++) {
        int t;
        cin >> t;
        if (t == 1) {
            int pos, val;
            cin >> pos >> val;
            pos--;
            if (pos != 0) {
                upd(0, 0, N - 1, min(h[pos], h[pos - 1]), max(h[pos], h[pos - 1]), -1);
            }
            if (pos != n - 1) {
                upd(0, 0, N - 1, min(h[pos], h[pos + 1]), max(h[pos], h[pos + 1]), -1);
            }
            h[pos] = val;
            if (pos != 0) {
                upd(0, 0, N - 1, min(h[pos], h[pos - 1]), max(h[pos], h[pos - 1]), 1);
            }
            if (pos != n - 1) {
                upd(0, 0, N - 1, min(h[pos], h[pos + 1]), max(h[pos], h[pos + 1]), 1);
            }
        } else {
            int hg;
            cin >> hg;
            cout << get(0, 0, N - 1, hg, hg) << '\n';
        }
    }
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 26 ms 24568 KB Output is correct
3 Correct 26 ms 24184 KB Output is correct
4 Correct 26 ms 24568 KB Output is correct
5 Correct 26 ms 24312 KB Output is correct
6 Correct 25 ms 24312 KB Output is correct
7 Correct 18 ms 19192 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 26 ms 24568 KB Output is correct
3 Correct 26 ms 24184 KB Output is correct
4 Correct 26 ms 24568 KB Output is correct
5 Correct 26 ms 24312 KB Output is correct
6 Correct 25 ms 24312 KB Output is correct
7 Correct 18 ms 19192 KB Output is correct
8 Correct 102 ms 1024 KB Output is correct
9 Correct 269 ms 34220 KB Output is correct
10 Correct 260 ms 34224 KB Output is correct
11 Correct 92 ms 1016 KB Output is correct
12 Correct 142 ms 2528 KB Output is correct
13 Correct 180 ms 34296 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 26 ms 24568 KB Output is correct
3 Correct 26 ms 24184 KB Output is correct
4 Correct 26 ms 24568 KB Output is correct
5 Correct 26 ms 24312 KB Output is correct
6 Correct 25 ms 24312 KB Output is correct
7 Correct 18 ms 19192 KB Output is correct
8 Correct 102 ms 1024 KB Output is correct
9 Correct 269 ms 34220 KB Output is correct
10 Correct 260 ms 34224 KB Output is correct
11 Correct 92 ms 1016 KB Output is correct
12 Correct 142 ms 2528 KB Output is correct
13 Correct 180 ms 34296 KB Output is correct
14 Correct 501 ms 34916 KB Output is correct
15 Correct 513 ms 35112 KB Output is correct
16 Correct 513 ms 35832 KB Output is correct
17 Correct 524 ms 35320 KB Output is correct
18 Correct 526 ms 35552 KB Output is correct