oj.uz

Submission #92516

# Submission time Handle Problem Language Result Execution time Memory
92516 2019-01-03T09:29:39 Z Randooom Simple game (IZhO17_game) C++14
100 / 100
 281 ms 11384 KB 
#include <bits/stdc++.h>
#define in freopen ("input.txt", "r", stdin);
#define out freopen("output.txt", "w", stdout);
#define ll long long int

const int val = (1e6) + 2;
const int inf = (1e6);
double eps = 0.000000001;

using namespace std;

int t[4000005], a[100005];

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

int get(int v, int l, int r, int pos){
    if(l == r) return t[v];
    int m = (l + r) / 2;
    if(pos <= m) return t[v] + get(v*2, l, m, pos);
    else return t[v] + get(v*2+1, m+1, r, pos);
}

int solve(){
    int n, m;
    cin >> n >> m;
    for(int i=1; i<=n; ++i){
        cin >> a[i];
    }
    for(int i=1; i<n; ++i){
        int l = min(a[i], a[i+1]);
        int r = max(a[i], a[i+1]);
        update(1, 1, inf, l, r, 1);
    }
    for(int i=1; i<=m; ++i){
        int q, x, y;
        cin >> q;
        if(q == 1){
            cin >> x >> y;
            if(x > 1){
                int l = min(a[x-1], a[x]);
                int r = max(a[x-1], a[x]);
                update(1, 1, inf, l, r, -1);
            }
            if(x < n){
                int l = min(a[x+1], a[x]);
                int r = max(a[x+1], a[x]);
                update(1, 1, inf, l, r, -1);
            }
            a[x] = y;
            if(x > 1){
                int l = min(a[x-1], a[x]);
                int r = max(a[x-1], a[x]);
                update(1, 1, inf, l, r, 1);
            }
            if(x < n){
                int l = min(a[x+1], a[x]);
                int r = max(a[x+1], a[x]);
                update(1, 1, inf, l, r, 1);
            }
        }
        else{
            cin >> x;
            cout << get(1, 1, inf, x) << endl;
        }
    }
}

int main(){
    //in out
	ios_base::sync_with_stdio(0);
    solve();
    return 0;
}

Compilation message

game.cpp: In function 'int solve()':
game.cpp:74:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 9 ms 6648 KB Output is correct
3 Correct 9 ms 6392 KB Output is correct
4 Correct 9 ms 6520 KB Output is correct
5 Correct 9 ms 6648 KB Output is correct
6 Correct 9 ms 6648 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 504 KB Output is correct
2 Correct 9 ms 6648 KB Output is correct
3 Correct 9 ms 6392 KB Output is correct
4 Correct 9 ms 6520 KB Output is correct
5 Correct 9 ms 6648 KB Output is correct
6 Correct 9 ms 6648 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 165 ms 1808 KB Output is correct
9 Correct 245 ms 11256 KB Output is correct
10 Correct 242 ms 11100 KB Output is correct
11 Correct 161 ms 1656 KB Output is correct
12 Correct 191 ms 2936 KB Output is correct
13 Correct 170 ms 2808 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 9 ms 6648 KB Output is correct
3 Correct 9 ms 6392 KB Output is correct
4 Correct 9 ms 6520 KB Output is correct
5 Correct 9 ms 6648 KB Output is correct
6 Correct 9 ms 6648 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 165 ms 1808 KB Output is correct
9 Correct 245 ms 11256 KB Output is correct
10 Correct 242 ms 11100 KB Output is correct
11 Correct 161 ms 1656 KB Output is correct
12 Correct 191 ms 2936 KB Output is correct
13 Correct 170 ms 2808 KB Output is correct
14 Correct 276 ms 11168 KB Output is correct
15 Correct 269 ms 11256 KB Output is correct
16 Correct 281 ms 11228 KB Output is correct
17 Correct 271 ms 11384 KB Output is correct
18 Correct 274 ms 11128 KB Output is correct