oj.uz

Submission #171547

# Submission time Handle Problem Language Result Execution time Memory
171547 2019-12-29T06:46:42 Z juggernaut Simple game (IZhO17_game) C++14
100 / 100
 489 ms 19448 KB 
//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

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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 18 ms 15096 KB Output is correct
3 Correct 18 ms 14712 KB Output is correct
4 Correct 18 ms 14844 KB Output is correct
5 Correct 18 ms 15096 KB Output is correct
6 Correct 18 ms 14968 KB Output is correct
7 Correct 13 ms 12792 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 18 ms 15096 KB Output is correct
3 Correct 18 ms 14712 KB Output is correct
4 Correct 18 ms 14844 KB Output is correct
5 Correct 18 ms 15096 KB Output is correct
6 Correct 18 ms 14968 KB Output is correct
7 Correct 13 ms 12792 KB Output is correct
8 Correct 132 ms 1864 KB Output is correct
9 Correct 248 ms 19312 KB Output is correct
10 Correct 260 ms 19340 KB Output is correct
11 Correct 133 ms 1656 KB Output is correct
12 Correct 173 ms 3464 KB Output is correct
13 Correct 131 ms 19192 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 18 ms 15096 KB Output is correct
3 Correct 18 ms 14712 KB Output is correct
4 Correct 18 ms 14844 KB Output is correct
5 Correct 18 ms 15096 KB Output is correct
6 Correct 18 ms 14968 KB Output is correct
7 Correct 13 ms 12792 KB Output is correct
8 Correct 132 ms 1864 KB Output is correct
9 Correct 248 ms 19312 KB Output is correct
10 Correct 260 ms 19340 KB Output is correct
11 Correct 133 ms 1656 KB Output is correct
12 Correct 173 ms 3464 KB Output is correct
13 Correct 131 ms 19192 KB Output is correct
14 Correct 460 ms 19420 KB Output is correct
15 Correct 489 ms 19392 KB Output is correct
16 Correct 461 ms 19320 KB Output is correct
17 Correct 466 ms 19444 KB Output is correct
18 Correct 469 ms 19448 KB Output is correct