oj.uz

Submission #171560

# Submission time Handle Problem Language Result Execution time Memory
171560 2019-12-29T08:26:46 Z mcdx9524 Simple game (IZhO17_game) C++14
49 / 100
 266 ms 68824 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];
    }
    if (n <= 1000) {
        for (int it = 0; it < m; it++) {
            int t;
            cin >> t;
            if (t == 1) {
                int pos, val;
                cin >> pos >> val;
                pos--;
                h[pos] = val;
            } else {
                int hg;
                cin >> hg;
                int res = 0;
                for (int i = 1; i < n; i++) {
                    if (hg >= min(h[i], h[i - 1]) && hg <= max(h[i], h[i - 1])) {
                        res++;
                    }
                }
                cout << res << '\n';
            }
        }
        return 0;
    }
    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) {
            assert(0);
            int pos, val;
            cin >> pos >> val;
            pos--;
            h[pos] = val;
        } 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 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 4 ms 376 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 4 ms 376 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 4 ms 376 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 4 ms 376 KB Output is correct
8 Correct 99 ms 1400 KB Output is correct
9 Correct 262 ms 35832 KB Output is correct
10 Correct 266 ms 35620 KB Output is correct
11 Correct 95 ms 1752 KB Output is correct
12 Correct 145 ms 3848 KB Output is correct
13 Correct 176 ms 35704 KB Output is correct

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 4 ms 376 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 4 ms 376 KB Output is correct
8 Correct 99 ms 1400 KB Output is correct
9 Correct 262 ms 35832 KB Output is correct
10 Correct 266 ms 35620 KB Output is correct
11 Correct 95 ms 1752 KB Output is correct
12 Correct 145 ms 3848 KB Output is correct
13 Correct 176 ms 35704 KB Output is correct
14 Runtime error 219 ms 68824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -