oj.uz

Submission #882902

# Submission time Handle Problem Language Result Execution time Memory
882902 2023-12-04T05:50:01 Z marcid Simple game (IZhO17_game) C++17
100 / 100
 150 ms 13056 KB 
#include <bits/stdc++.h>
using namespace std;
int const maxn = 1e6 + 9;
int a[maxn];
int tree[maxn << 2];
void push(int v, int l, int r) {
    if(l != r) {
        tree[v << 1] += tree[v];
        tree[v << 1 | 1] += tree[v];
        tree[v] = 0;
    } 
}
void upd(int v, int tl, int tr, int l, int r, int x) {
    if(tr < l || tl > r) {
        return;
    }
    push(v, tl, tr);
    if(l <= tl && tr <= r) {
        tree[v] += x;
        push(v, tl, tr);
        return;
    }
    int tm = tl + tr >> 1;
    upd(v << 1, tl, tm, l, r, x);
    upd(v << 1 | 1, tm + 1, tr, l, r, x);
}
int get(int v, int tl, int tr, int k) {
    push(v, tl, tr);
    if(tl == tr) 
        return tree[v];
    int tm = tl + tr >> 1;
    return k <= tm ? get(v << 1, tl, tm, k) : get(v << 1 | 1, tm + 1, tr, k); 
    
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    cin >> n >> m >> a[1];
    for(int i = 2; i <= n; i ++) {
        cin >> a[i];
        upd(1, 1, maxn - 1, min(a[i - 1], a[i]), max(a[i - 1], a[i]), 1);
    }
    while(m --) {
        int t, i;
        cin >> t >> i;
        if(t == 2) {
            cout << get(1, 1, maxn - 1, i) << '\n';
            continue;
        }
        int v;
        cin >> v;
        if(i > 1) {
            upd(1, 1, maxn - 1, min(a[i - 1], a[i]), max(a[i - 1], a[i]), -1);
            upd(1, 1, maxn - 1, min(a[i - 1], v), max(a[i - 1], v), 1);
        }
        if(i < n) {
            upd(1, 1, maxn - 1, min(a[i + 1], a[i]), max(a[i + 1], a[i]), -1);
            upd(1, 1, maxn - 1, min(a[i + 1], v), max(a[i + 1], v), 1);
        }
        a[i] = v;
    }
}

Compilation message

game.cpp: In function 'void upd(int, int, int, int, int, int)':
game.cpp:23:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |     int tm = tl + tr >> 1;
      |              ~~~^~~~
game.cpp: In function 'int get(int, int, int, int)':
game.cpp:31:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |     int tm = tl + tr >> 1;
      |              ~~~^~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 3 ms 10712 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 3 ms 10712 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 43 ms 7592 KB Output is correct
9 Correct 72 ms 13036 KB Output is correct
10 Correct 72 ms 12880 KB Output is correct
11 Correct 40 ms 7440 KB Output is correct
12 Correct 61 ms 8532 KB Output is correct
13 Correct 52 ms 12888 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 3 ms 10712 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 43 ms 7592 KB Output is correct
9 Correct 72 ms 13036 KB Output is correct
10 Correct 72 ms 12880 KB Output is correct
11 Correct 40 ms 7440 KB Output is correct
12 Correct 61 ms 8532 KB Output is correct
13 Correct 52 ms 12888 KB Output is correct
14 Correct 137 ms 13036 KB Output is correct
15 Correct 138 ms 13040 KB Output is correct
16 Correct 147 ms 13056 KB Output is correct
17 Correct 150 ms 13040 KB Output is correct
18 Correct 150 ms 12880 KB Output is correct