oj.uz

Submission #137188

# Submission time Handle Problem Language Result Execution time Memory
137188 2019-07-27T08:13:26 Z meatrow Simple game (IZhO17_game) C++17
100 / 100
 219 ms 11340 KB 
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
//#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

const int N = 1e6 + 5;

int t[N * 4];

void update(int v, int tl, int tr, int l, int r, int add) {
    if (l > r)
        return;
    if (l == tl && r == tr) {
        t[v] += add;
    } else {
        int tm = (tl + tr) / 2;
        update(v*2, tl, tm, l, min(r, tm), add);
        update(v*2+1, tm+1, tr, max(l, tm+1), r, add);
    }
}

int get(int v, int tl, int tr, int pos) {
    if (tl == tr)
        return t[v];
    int tm = (tl + tr) / 2;
    if (pos <= tm)
        return t[v] + get(v*2, tl, tm, pos);
    else
        return t[v] + get(v*2+1, tm+1, tr, pos);
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
        if (i) {
            update(1, 0, N - 1, min(h[i], h[i - 1]), max(h[i], h[i - 1]), 1);
        }
    }
    while (m--) {
        int type;
        cin >> type;
        if (type == 1) {
            int i, val;
            cin >> i >> val;
            i--;
            if (i) {
                update(1, 0, N - 1, min(h[i], h[i - 1]), max(h[i], h[i - 1]), -1);
            }
            if (i + 1 < n) {
                update(1, 0, N - 1, min(h[i], h[i + 1]), max(h[i], h[i + 1]), -1);
            }
            h[i] = val;
            if (i) {
                update(1, 0, N - 1, min(h[i], h[i - 1]), max(h[i], h[i - 1]), 1);
            }
            if (i + 1 < n) {
                update(1, 0, N - 1, min(h[i], h[i + 1]), max(h[i], h[i + 1]), 1);
            }
        } else {
            int x;
            cin >> x;
            cout << get(1, 0, N - 1, x) << '\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 9 ms 6652 KB Output is correct
3 Correct 9 ms 6456 KB Output is correct
4 Correct 9 ms 6520 KB Output is correct
5 Correct 9 ms 6552 KB Output is correct
6 Correct 9 ms 6520 KB Output is correct
7 Correct 5 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 9 ms 6652 KB Output is correct
3 Correct 9 ms 6456 KB Output is correct
4 Correct 9 ms 6520 KB Output is correct
5 Correct 9 ms 6552 KB Output is correct
6 Correct 9 ms 6520 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 50 ms 1744 KB Output is correct
9 Correct 121 ms 11220 KB Output is correct
10 Correct 123 ms 11128 KB Output is correct
11 Correct 45 ms 1576 KB Output is correct
12 Correct 81 ms 3000 KB Output is correct
13 Correct 79 ms 2808 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 9 ms 6652 KB Output is correct
3 Correct 9 ms 6456 KB Output is correct
4 Correct 9 ms 6520 KB Output is correct
5 Correct 9 ms 6552 KB Output is correct
6 Correct 9 ms 6520 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 50 ms 1744 KB Output is correct
9 Correct 121 ms 11220 KB Output is correct
10 Correct 123 ms 11128 KB Output is correct
11 Correct 45 ms 1576 KB Output is correct
12 Correct 81 ms 3000 KB Output is correct
13 Correct 79 ms 2808 KB Output is correct
14 Correct 214 ms 11328 KB Output is correct
15 Correct 214 ms 11192 KB Output is correct
16 Correct 219 ms 11212 KB Output is correct
17 Correct 217 ms 11340 KB Output is correct
18 Correct 216 ms 11196 KB Output is correct