Submission #333893

#	Time	Username	Problem	Language	Result	Execution time	Memory
333893		juggernaut	Simple game (IZhO17_game)	C++14	100 / 100	424 ms	19564 KiB

game

#include<bits/stdc++.h>
using namespace std;
const int mx=1e6;
int n,q,h[100005],tree[mx<<2],flag[mx<<2];
void push(int v,int l,int r){
    if(l!=r){
        flag[v<<1]+=flag[v];
        flag[v<<1|1]+=flag[v];
    }
    tree[v]+=flag[v]*(r-l+1);
    flag[v]=0;
}
void update(int v,int l,int r,int ql,int qr,int val){
    if(qr<l||r<ql)return;
    if(ql<=l&&r<=qr){
        flag[v]+=val;
        return;
    }
    push(v,l,r);
    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 pos){
    if(pos<l||pos>r)return 0;
    push(v,l,r);
    if(l==r)return tree[v];
    int mid=(l+r)>>1;
    return get(v<<1,l,mid,pos)+get(v<<1|1,mid+1,r,pos);
}
void upd(int l,int r,int val){
    if(l>r)swap(l,r);
    update(1,1,mx,l,r,val);
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d",&h[i]);
    for(int i=2;i<=n;i++)upd(h[i-1],h[i],1);
    while(q--){
        int type;
        scanf("%d",&type);
        if(type&1){
            int pos,val;
            scanf("%d%d",&pos,&val);
            if(pos>1)upd(h[pos],h[pos-1],-1);
            if(pos<n)upd(h[pos],h[pos+1],-1);
            h[pos]=val;
            if(pos>1)upd(h[pos],h[pos-1],1);
            if(pos<n)upd(h[pos],h[pos+1],1);
        }else{
            int x;
            scanf("%d",&x);
            printf("%d\n",get(1,1,mx,x));
        }
    }
}

Compilation message (stderr)

game.cpp: In function 'int main()':
game.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |     scanf("%d%d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~
game.cpp:38:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |     for(int i=1;i<=n;i++)scanf("%d",&h[i]);
      |                          ~~~~~^~~~~~~~~~~~
game.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |         scanf("%d",&type);
      |         ~~~~~^~~~~~~~~~~~
game.cpp:45:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |             scanf("%d%d",&pos,&val);
      |             ~~~~~^~~~~~~~~~~~~~~~~~
game.cpp:53:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |             scanf("%d",&x);
      |             ~~~~~^~~~~~~~~

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