oj.uz

Submission #577511

# Submission time Handle Problem Language Result Execution time Memory
577511 2022-06-15T02:49:35 Z gg123_pe Simple game (IZhO17_game) C++14
0 / 100
 5 ms 6612 KB 
#include <bits/stdc++.h>
using namespace std; 

typedef long long ll; 
#define f(i,a,b) for(int i = a; i < b; i++)
#define fa(i,a,b) for(int i = a; i >= b; i--)

const int N = 1e5 + 5, M = 1e6 + 5, mod = 1e9 + 7; 


int n, m, a[N]; 

struct bit{
    int bit[M]; 

    void upd(int x, int val){
        for(; x < M; x = (x|(x+1))) bit[x] += val;
    }

    int get(int x){
        int ans = 0;
        for(; x >= 0; x = (x&(x+1)) - 1) ans += bit[x];  
        return ans; 
    }

    int que(int l, int r){
        return get(r) - get(l-1); 
    }

}L, R; 


void go(int i, int k){
    int x, y; 
    x = min(a[i], a[i+1]), y = max(a[i], a[i+1]); 
    L.upd(x, k);        
    R.upd(y, k);         
}

int main(){
    cin >> n >> m; 

    f(i,1,n+1) cin >> a[i]; 

    f(i,1,n){
        go(i, 1); 
    }

    while(m--){
        int t, i, val; cin >> t;

        if(t == 1){
            cin >> i >> val; 

            if(i >= 2) go(i-1, -1);
            go(i, -1); 

            a[i] = val; 

            if(i >= 2) go(i-1, 1); 
            go(i, 1); 
        }
        else{
            cin >> i; 

            int ans = n-1; 

            ans -= (L.que(i+1, M-1) + R.que(0, i-1));
        
            cout << ans << "\n"; 
        }
    }
    return 0; 
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 5 ms 6612 KB Output is correct
3 Correct 5 ms 6612 KB Output is correct
4 Incorrect 5 ms 6612 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 5 ms 6612 KB Output is correct
3 Correct 5 ms 6612 KB Output is correct
4 Incorrect 5 ms 6612 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 5 ms 6612 KB Output is correct
3 Correct 5 ms 6612 KB Output is correct
4 Incorrect 5 ms 6612 KB Output isn't correct
5 Halted 0 ms 0 KB -