oj.uz

Submission #344294

# Submission time Handle Problem Language Result Execution time Memory
344294 2021-01-05T12:49:27 Z fixikmila Simple game (IZhO17_game) C++14
0 / 100
 1 ms 364 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 b[1000001],tree[4000005];
void update(ll l,ll x,ll v,ll tl,ll tr){
    if(l==tl&&tl==tr)tree[v]+=x,b[l]+=x;
    else if(tl>l||tr<l)return;
    else{
        ll tm=(tl+tr)/2;
        update(l,x,2*v,tl,tm),update(l,x,2*v+1,tm+1,tr);
        tree[v]=tree[2*v]+tree[2*v+1];
    }
}
ll get_sum(ll l,ll r,ll v,ll tl,ll tr){
    if(tl>=l&&tr<=r)return tree[v];
        else if(tl>r||tr<l)return 0;
    ll tm=(tl+tr)/2;
    return get_sum(l,r,2*v,tl,tm)+get_sum(l,r,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,0,n-1);
        update(r,-1,1,0,n-1);
    }
   // cout<<get_sum(0,3,1,0,n-1)<<endl;
    while(m--){
        cin>>z;
        if(z==1){
                cin>>x>>y;
        x--;
        if(x){
            l=a[x-1],r=a[x];
            if(l>r)swap(l,r);
        update(l,-1,1,0,n-1);
        update(r,1,1,0,n-1);
        }
        if(x<n-1){
            l=a[x+1],r=a[x];
            if(l>r)swap(l,r);
        update(l,-1,1,0,n-1);
        update(r,1,1,0,n-1);
            }
        a[x]=y;
        if(x){
            l=a[x-1],r=a[x];
            if(l>r)swap(l,r);
        update(l,1,1,0,n-1);
        update(r,-1,1,0,n-1);
        }
        if(x<n-1){
            l=a[x+1],r=a[x];
            if(l>r)swap(l,r);
        update(l,1,1,0,n-1);
        update(r,-1,1,0,n-1);
            }
        }
        else{
            cin>>x;
            ans=get_sum(0,x,1,0,n-1);
            cout<<ans;
            cout<<"\n";
        }
    }
    return 0;
}

Compilation message

game.cpp: In function 'int main()':
game.cpp:37:8: warning: unused variable 't' [-Wunused-variable]
   37 |     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:37:16: warning: unused variable 'k' [-Wunused-variable]
   37 |     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:37:20: warning: unused variable 'sum' [-Wunused-variable]
   37 |     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:37:52: warning: unused variable 'mn' [-Wunused-variable]
   37 |     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:37:65: warning: unused variable 'mx' [-Wunused-variable]
   37 |     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 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

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

Subtask #3
0 / 51.0

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