oj.uz

Submission #524168

# Submission time Handle Problem Language Result Execution time Memory
524168 2022-02-08T18:16:39 Z nickmet2004 Simple game (IZhO17_game) C++11
0 / 100
 1 ms 460 KB 
#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
int n,m, a[N],  F[200005];
void upd(int i , int d){
    while(i <= n){
        F[i] += d;
        i += i & -i;
    }
}
int get(int i){
    int s= 0;
    while(i){
        s += F[i] , i -= i&-i;
    }
    return s;
}
void M(int A , int p , int h){
    if(A > h){
        upd(h , +1);
        if(a[p] >= A){
            upd(a[p] + 1 , +1);
            upd(A , -2);
        }
        else {
            upd(a[p] , -1);
        }
    }else {
        upd(h + 1 , -1);
        if(a[p] >= A){
            upd(a[p]+ 1 , +1);
        }else {
            upd(a[p] , -1);
            upd(A+1 , +2);
        }
    }
}
int main (){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n>>m;
    for(int i =1; i<= n; ++i)cin>>a[i];
    for(int i = 1; i< n; ++i){
        int x = a[i] , y = a[i + 1];
        if(x > y)swap(x , y);
        upd(x , 1),
        upd(y + 1 ,-1);
    }
    while(m--){
        int x;
        cin >> x;
        if(x==1){
            int p , h;
            cin >> p >> h;
            int A=-1 , B=-1;
            if(p==1) A = a[p+1];
            else if(p==n) B = a[p-1];
            else A = a[p-1] , B = a[p+1];
            if(A != -1)M(A , p , h);
            if(B != -1) M(B , p , h);
            a[p]=h;
        }else {
            int h;cin>>h;
            cout << get(h)<<endl;
        }
    }

return 0;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Runtime error 1 ms 460 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Runtime error 1 ms 460 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Runtime error 1 ms 460 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -