Submission #171547

#	Time	Username	Problem	Language	Result	Execution time	Memory
171547		juggernaut	Simple game (IZhO17_game)	C++14	100 / 100	489 ms	19448 KiB

game

//Just try and the idea will come!
#include<bits/stdc++.h>
using namespace std;
const int h=1000000;
int n,m,tree[h*4],mx,a[100001],i,flag[h*4],type,x,y;
void push(int v,int l,int r){
    if(l!=r){
        flag[(v<<1)]+=flag[v];
        flag[(v<<1)+1]+=flag[v];
    }
    tree[v]+=(r-l+1)*flag[v];
    flag[v]=0;
}
void update(int v,int l,int r,int ql,int qr,int val){
    push(v,l,r);
    if(r<ql||qr<l)return;
    if(ql<=l&&r<=qr){
        flag[v]+=val;
        push(v,l,r);
        return;
    }
    int mid=(l+r)>>1;
    update((v<<1),l,mid,ql,qr,val);
    update((v<<1)+1,mid+1,r,ql,qr,val);
    tree[v]=tree[(v<<1)]+tree[(v<<1)+1];
}
int get(int v,int l,int r,int ql,int qr){
    push(v,l,r);
    if(ql<=l&&r<=qr)return tree[v];
    if(r<ql||qr<l)return 0;
    int mid=(l+r)>>1;
    return get((v<<1),l,mid,ql,qr)+get((v<<1)+1,mid+1,r,ql,qr);
}
void update(int a,int b,int val){
    if(a>b)swap(a,b);
    update(1,1,h,a,b,val);
}
main(){
    scanf("%d%d",&n,&m);
    scanf("%d",&a[1]);
    for(i=2;i<=n;i++)scanf("%d",&a[i]),update(a[i-1],a[i],1);
    while(m--){
        scanf("%d",&type);
        if(type&1){
            scanf("%d%d",&x,&y);
            if(x>1)update(a[x-1],a[x],-1);
            if(x<n)update(a[x],a[x+1],-1);
            a[x]=y;
            if(x>1)update(a[x-1],a[x],1);
            if(x<n)update(a[x],a[x+1],1);
        }else{
            scanf("%d",&x);
            printf("%d\n",get(1,1,h,x,x));
        }
    }
}

Compilation message (stderr)

game.cpp:38:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
game.cpp: In function 'int main()':
game.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
game.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&a[1]);
     ~~~~~^~~~~~~~~~~~
game.cpp:41:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=2;i<=n;i++)scanf("%d",&a[i]),update(a[i-1],a[i],1);
                      ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
game.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&type);
         ~~~~~^~~~~~~~~~~~
game.cpp:45:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d",&x,&y);
             ~~~~~^~~~~~~~~~~~~~
game.cpp:52:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&x);
             ~~~~~^~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51