oj.uz

Submission #170258

# Submission time Handle Problem Language Result Execution time Memory
170258 2019-12-24T12:09:52 Z nvmdava Simple game (IZhO17_game) C++17
100 / 100
 91 ms 7032 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define N 1000005

int fen[N];

void update(int x, int v){
    while(x < N){
        fen[x] += v;
        x += x & -x;
    }
}

int get(int x){
    int s = 0;
    while(x){
        s += fen[x];
        x -= x & -x;
    }
    return s;
}

int h[N];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin>>n>>m;

    for(int i = 1; i <= n; ++i){
        cin>>h[i];
    }
    for(int i = 2; i <= n; ++i){
        update(min(h[i], h[i - 1]), 1);
        update(max(h[i], h[i - 1]), -1);
    }
    while(m--){
        int t;
        cin>>t;
        if(t == 2){
            int a;
            cin>>a;
            cout<<get(a)<<'\n';
        } else {
            int i, x;
            cin>>i>>x;
            if(i != 1){
                update(min(h[i], h[i - 1]), -1);
                update(max(h[i], h[i - 1]), 1);
            }
            if(i != n){
                update(min(h[i], h[i + 1]), -1);
                update(max(h[i], h[i + 1]), 1);
            }
            h[i] = x;
            if(i != 1){
                update(min(h[i], h[i - 1]), 1);
                update(max(h[i], h[i - 1]), -1);
            }
            if(i != n){
                update(min(h[i], h[i + 1]), 1);
                update(max(h[i], h[i + 1]), -1);
            }
        }
    }
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 6 ms 4216 KB Output is correct
3 Correct 5 ms 4088 KB Output is correct
4 Correct 5 ms 4088 KB Output is correct
5 Correct 5 ms 4112 KB Output is correct
6 Correct 5 ms 4088 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 504 KB Output is correct
2 Correct 6 ms 4216 KB Output is correct
3 Correct 5 ms 4088 KB Output is correct
4 Correct 5 ms 4088 KB Output is correct
5 Correct 5 ms 4112 KB Output is correct
6 Correct 5 ms 4088 KB Output is correct
7 Correct 4 ms 376 KB Output is correct
8 Correct 47 ms 1788 KB Output is correct
9 Correct 56 ms 6868 KB Output is correct
10 Correct 55 ms 6904 KB Output is correct
11 Correct 47 ms 1656 KB Output is correct
12 Correct 49 ms 2936 KB Output is correct
13 Correct 51 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 6 ms 4216 KB Output is correct
3 Correct 5 ms 4088 KB Output is correct
4 Correct 5 ms 4088 KB Output is correct
5 Correct 5 ms 4112 KB Output is correct
6 Correct 5 ms 4088 KB Output is correct
7 Correct 4 ms 376 KB Output is correct
8 Correct 47 ms 1788 KB Output is correct
9 Correct 56 ms 6868 KB Output is correct
10 Correct 55 ms 6904 KB Output is correct
11 Correct 47 ms 1656 KB Output is correct
12 Correct 49 ms 2936 KB Output is correct
13 Correct 51 ms 2808 KB Output is correct
14 Correct 87 ms 6936 KB Output is correct
15 Correct 77 ms 7004 KB Output is correct
16 Correct 81 ms 6840 KB Output is correct
17 Correct 78 ms 7032 KB Output is correct
18 Correct 91 ms 6952 KB Output is correct