Submission #36953

#	Time	Username	Problem	Language	Result	Execution time	Memory
36953		top34051	Simple game (IZhO17_game)	C++14	100 / 100	159 ms	6312 KiB

game

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;
const int maxv = 1e6;

int n,m;
int p[maxn], tree[maxv+5];

void add(int x,int val) {
    while(x<=maxv) {
        tree[x] += val;
        x += x&-x;
    }
}

int sum(int x) {
    int ans = 0;
    while(x>0) {
        ans += tree[x];
        x -= x&-x;
    }
    return ans;
}

void update(int x,int y,int val) {
    if(x>y) swap(x,y);
    add(x,val); add(y+1,-val);
}

int main() {
    int type,x,val;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&p[i]);
    for(int i=1;i<n;i++) update(p[i], p[i+1], 1);
    while(m--) {
        scanf("%d",&type);
        if(type==1) {
            scanf("%d%d",&x,&val);
            if(x>1) update(p[x-1], p[x], -1);
            if(x<n) update(p[x], p[x+1], -1);
            p[x] = val;
            if(x>1) update(p[x-1], p[x], 1);
            if(x<n) update(p[x], p[x+1], 1);
        }
        else {
            scanf("%d",&x);
            printf("%d\n",sum(x));
        }
    }
}

Compilation message (stderr)

game.cpp: In function 'int main()':
game.cpp:33:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
                        ^
game.cpp:34:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++) scanf("%d",&p[i]);
                                            ^
game.cpp:37:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&type);
                          ^
game.cpp:39:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d",&x,&val);
                                  ^
game.cpp:47:27: 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