oj.uz

Submission #877732

# Submission time Handle Problem Language Result Execution time Memory
877732 2023-11-23T13:29:59 Z Husayn Simple game (IZhO17_game) C++14
100 / 100
 150 ms 13112 KB 
#include <bits/stdc++.h>
using namespace std;
int const maxn = 1e6 + 9;
int a[maxn];
int lazy[maxn << 2];
void push(int v, int l, int r) {
    if(l != r) {
        lazy[v << 1] += lazy[v];
        lazy[v << 1 | 1] += lazy[v];
        lazy[v] = 0;
    } 
}
void updateRange(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) {
        lazy[v] += x;
        push(v, tl, tr);
        return;
    }
    int tm = tl + tr >> 1;
    updateRange(v << 1, tl, tm, l, r, x);
    updateRange(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 lazy[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];
        updateRange(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) {
            updateRange(1, 1, maxn - 1, min(a[i - 1], a[i]), max(a[i - 1], a[i]), -1);
            updateRange(1, 1, maxn - 1, min(a[i - 1], v), max(a[i - 1], v), 1);
        }
        if(i < n) {
            updateRange(1, 1, maxn - 1, min(a[i + 1], a[i]), max(a[i + 1], a[i]), -1);
            updateRange(1, 1, maxn - 1, min(a[i + 1], v), max(a[i + 1], v), 1);
        }
        a[i] = v;
    }
    return 0;
}

Compilation message

game.cpp: In function 'void updateRange(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 6744 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 3 ms 10844 KB Output is correct
4 Correct 3 ms 10924 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 11096 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 3 ms 10844 KB Output is correct
4 Correct 3 ms 10924 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 11096 KB Output is correct
8 Correct 39 ms 7384 KB Output is correct
9 Correct 72 ms 12920 KB Output is correct
10 Correct 86 ms 12884 KB Output is correct
11 Correct 39 ms 7448 KB Output is correct
12 Correct 61 ms 8560 KB Output is correct
13 Correct 59 ms 12704 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 3 ms 10844 KB Output is correct
4 Correct 3 ms 10924 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 11096 KB Output is correct
8 Correct 39 ms 7384 KB Output is correct
9 Correct 72 ms 12920 KB Output is correct
10 Correct 86 ms 12884 KB Output is correct
11 Correct 39 ms 7448 KB Output is correct
12 Correct 61 ms 8560 KB Output is correct
13 Correct 59 ms 12704 KB Output is correct
14 Correct 150 ms 12944 KB Output is correct
15 Correct 138 ms 12956 KB Output is correct
16 Correct 138 ms 13052 KB Output is correct
17 Correct 147 ms 13112 KB Output is correct
18 Correct 138 ms 13052 KB Output is correct