oj.uz

Submission #492339

# Submission time Handle Problem Language Result Execution time Memory
492339 2021-12-06T18:24:36 Z infertechno2 Simple game (IZhO17_game) C++17
100 / 100
 232 ms 19800 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int Size=1e6+10;

ll y[Size],seg_tree[4*Size];

void update(ll l,ll r,ll i,ll tl,ll tr,ll val){
    if(l>tr or r<tl){
        return;
    }
    if(l==tl and r==tr){
        seg_tree[i]+=val;
    }else{
        ll mid=(l+r)/2;
        update(l,mid,i*2,tl,min(mid,tr),val);
        update(mid+1,r,i*2+1,max(mid+1,tl),tr,val);
    }
}
ll query(ll l,ll r,ll i,ll pos){
    if(l==r and l==pos){
        return seg_tree[i];
    }else{
        ll mid=(l+r)/2;
        if(pos<=mid){
            return query(l,mid,i*2,pos)+seg_tree[i];
        }else{
            return query(mid+1,r,i*2+1,pos)+seg_tree[i];
        }
    }
}


void solve(){
    ll n,m;
    cin>>n>>m;
    for(ll i=0;i<n;i++){
        cin>>y[i];
    }
    for(ll i=0;i<n-1;i++){
        update(1,Size-10,1,min(y[i],y[i+1]),max(y[i],y[i+1]),1);
    }
    while(m--){
        ll type;
        cin>>type;
        if(type==1){
            ll i,val;
            cin>>i>>val;
            i--;
            if(i!=0){
                update(1,Size-10,1,min(y[i-1],y[i]),max(y[i-1],y[i]),-1);
                update(1,Size-10,1,min(y[i-1],val),max(y[i-1],val),1);
            }
            if(i!=n-1){
                update(1,Size-10,1,min(y[i],y[i+1]),max(y[i],y[i+1]),-1);
                update(1,Size-10,1,min(val,y[i+1]),max(val,y[i+1]),1);
            }
            y[i]=val;
        }
        if(type==2){
            ll h;
            cin>>h;
            cout<<query(1,Size-10,1,h)<<endl;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll t=1;
    while(t--){
        solve();
    }
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 7 ms 9292 KB Output is correct
4 Correct 6 ms 9292 KB Output is correct
5 Correct 6 ms 9420 KB Output is correct
6 Correct 6 ms 9548 KB Output is correct
7 Correct 3 ms 332 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 7 ms 9292 KB Output is correct
4 Correct 6 ms 9292 KB Output is correct
5 Correct 6 ms 9420 KB Output is correct
6 Correct 6 ms 9548 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 145 ms 2048 KB Output is correct
9 Correct 220 ms 19656 KB Output is correct
10 Correct 203 ms 19680 KB Output is correct
11 Correct 139 ms 1912 KB Output is correct
12 Correct 172 ms 3680 KB Output is correct
13 Correct 154 ms 3140 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 7 ms 9292 KB Output is correct
4 Correct 6 ms 9292 KB Output is correct
5 Correct 6 ms 9420 KB Output is correct
6 Correct 6 ms 9548 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 145 ms 2048 KB Output is correct
9 Correct 220 ms 19656 KB Output is correct
10 Correct 203 ms 19680 KB Output is correct
11 Correct 139 ms 1912 KB Output is correct
12 Correct 172 ms 3680 KB Output is correct
13 Correct 154 ms 3140 KB Output is correct
14 Correct 223 ms 19672 KB Output is correct
15 Correct 231 ms 19800 KB Output is correct
16 Correct 226 ms 19668 KB Output is correct
17 Correct 232 ms 19724 KB Output is correct
18 Correct 232 ms 19692 KB Output is correct