oj.uz

Submission #577512

# Submission time Handle Problem Language Result Execution time Memory
577512 2022-06-15T02:53:34 Z gg123_pe Simple game (IZhO17_game) C++14
100 / 100
 251 ms 10764 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);
            if(i <= n-1) go(i, -1); 

            a[i] = val; 

            if(i >= 2) go(i-1, 1); 
            if(i <= n-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
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 4 ms 6612 KB Output is correct
3 Correct 6 ms 6612 KB Output is correct
4 Correct 5 ms 6576 KB Output is correct
5 Correct 5 ms 6588 KB Output is correct
6 Correct 5 ms 6740 KB Output is correct
7 Correct 4 ms 340 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 4 ms 6612 KB Output is correct
3 Correct 6 ms 6612 KB Output is correct
4 Correct 5 ms 6576 KB Output is correct
5 Correct 5 ms 6588 KB Output is correct
6 Correct 5 ms 6740 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 183 ms 1744 KB Output is correct
9 Correct 251 ms 10672 KB Output is correct
10 Correct 233 ms 10636 KB Output is correct
11 Correct 175 ms 1740 KB Output is correct
12 Correct 213 ms 2928 KB Output is correct
13 Correct 210 ms 2760 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 4 ms 6612 KB Output is correct
3 Correct 6 ms 6612 KB Output is correct
4 Correct 5 ms 6576 KB Output is correct
5 Correct 5 ms 6588 KB Output is correct
6 Correct 5 ms 6740 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 183 ms 1744 KB Output is correct
9 Correct 251 ms 10672 KB Output is correct
10 Correct 233 ms 10636 KB Output is correct
11 Correct 175 ms 1740 KB Output is correct
12 Correct 213 ms 2928 KB Output is correct
13 Correct 210 ms 2760 KB Output is correct
14 Correct 188 ms 10716 KB Output is correct
15 Correct 203 ms 10612 KB Output is correct
16 Correct 184 ms 10668 KB Output is correct
17 Correct 188 ms 10712 KB Output is correct
18 Correct 225 ms 10764 KB Output is correct