oj.uz

Submission #344445

# Submission time Handle Problem Language Result Execution time Memory
344445 2021-01-05T19:41:21 Z fixikmila Simple game (IZhO17_game) C++14
0 / 100
 10 ms 11884 KB 
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,ll>pll;
typedef long double ld;
ll bin_pow(ll a,ll b){
    if(b==0)return 1;
    if(b%2==0){
        ll t=bin_pow(a,b/2);
        return t*t%MOD;
    }
    else return a*bin_pow(a,b-1)%MOD;
}
ll sum[4000005];
void update(int idx,int val,int v,int tl,int tr){
if(idx==tl&&tl==tr){
    sum[v]+=val;
    return;
}
if(tl>idx||tr<idx)return;
int tm=(tl+tr)/2;
update(idx,val,2*v,tl,tm),update(idx,val,2*v+1,tm+1,tr);
sum[v]=sum[2*v]+sum[2*v+1];
}
ll sum1(int idx,int v,int tl,int tr){
    if(tl>=0&&tr<=idx)return sum[v];
    if(tl>idx||tr<0)return 0;
    int tm=(tl+tr)/2;
    return sum1(idx,2*v,tl,tm)+sum1(idx,2*v+1,tm+1,tr);
}
int main()
{
    //freopen("stones.in","r",stdin);
    //freopen("stones.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
    cin>>n>>m;
    vector<ll>a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=1;i<n;i++){
        l=a[i-1],r=a[i];
        if(l>r)swap(l,r);
        update(l+1,1,1,0,1e6);
        update(r,-1,1,0,1e6);
    }
    while(m--){
        cin>>z;
        if(z==1){
                cin>>x>>y;
        x--;
        update(a[x],-1,1,0,1e6);
        update(a[x]+1,1,1,0,1e6);
        if(x){
            l=a[x-1],r=a[x];
            if(l>r)swap(l,r);
        update(l+1,-1,1,0,1e6);
        update(r,1,1,0,1e6);
        }
        if(x<n-1){
            l=a[x+1],r=a[x];
            if(l>r)swap(l,r);
        update(l+1,-1,1,0,1e6);
        update(r,1,1,0,1e6);
            }
        a[x]=y;
        if(x){
            l=a[x-1],r=a[x];
            if(l>r)swap(l,r);
        update(l+1,1,1,0,1e6);
        update(r,-1,1,0,1e6);
        }
        if(x<n-1){
            l=a[x+1],r=a[x];
            if(l>r)swap(l,r);
        update(l+1,1,1,0,1e6);
        update(r,-1,1,0,1e6);
            }
            update(a[x],1,1,0,1e6);
        update(a[x]+1,-1,1,0,1e6);
        }
        else{
            cin>>x;
            ans=sum1(x,1,0,1e6);
            cout<<ans;
            cout<<"\n";
        }
    }
    return 0;
}

Compilation message

game.cpp: In function 'int main()':
game.cpp:38:8: warning: unused variable 't' [-Wunused-variable]
   38 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |        ^
game.cpp:38:16: warning: unused variable 'k' [-Wunused-variable]
   38 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                ^
game.cpp:38:20: warning: unused variable 'sum' [-Wunused-variable]
   38 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                    ^~~
game.cpp:38:52: warning: unused variable 'mn' [-Wunused-variable]
   38 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                                                    ^~
game.cpp:38:65: warning: unused variable 'mx' [-Wunused-variable]
   38 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                                                                 ^~

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 10 ms 11884 KB Output is correct
3 Incorrect 10 ms 11500 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 10 ms 11884 KB Output is correct
3 Incorrect 10 ms 11500 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 10 ms 11884 KB Output is correct
3 Incorrect 10 ms 11500 KB Output isn't correct
4 Halted 0 ms 0 KB -