Submission #38357

#	Time	Username	Problem	Language	Result	Execution time	Memory
38357		Just_Solve_The_Problem	Simple game (IZhO17_game)	C++11	100 / 100	436 ms	71424 KiB

game

#include <stdio.h>

using namespace std;

typedef long long ll;

const int inf = (int)1e9 + 7;
const int N = (int)1e6 + 7;

#define fr first
#define sc second
#define OK puts("OK");
#define eb emplace_back
#define mk make_pair
#define sz(s) ((int)s.size())

ll a[N];
ll t[4 * N];
ll add[4* N];

void push (int v) {
    add[(v << 1)] += add[v];
    add[(v << 1) + 1] += add[v];
    add[v] = 0;
}


ll get (int v, int l, int r, int pos) {
    if (l == r) {
        return add[v];
    } else {
        int m = (l + r) >> 1;
        push(v);
        if (pos <= m) {
            return get((v << 1), l, m, pos);
        } else {
            return get((v << 1)  + 1, m + 1, r, pos);
        }
    }
}


void up (int v, int l, int r, int tl, int tr, int ad) {
    if (tl != tr) {
        push (v);
    }
    if (tr < l || tl > r) {
        return ;
    }
    if (l <= tl && tr <= r) {
        add[v] += ad;
    } else {
        int tm = (tl + tr) >> 1;
        up((v << 1), l, r, tl, tm, ad);
        up((v << 1) + 1, l, r, tm + 1, tr, ad);
    }
}

ll max(ll a, ll b) { return a < b ? b : a; }
ll min(ll a, ll b) { return a < b ? a : b; }

main () {
    int n, m; scanf ("%d %d", &n, &m);

    for (int i = 1; i <= n; i++) {
        scanf ("%lld", a + i);
    }
    for (int i = 2; i <= n; i++) {
        up(1, min(a[i - 1], a[i]), max(a[i - 1], a[i]), 1, (int)1e6, 1);
//        printf ("%lld %lld\n", min(a[i - 1], a[i]), max(a[i - 1], a[i]));
    }
    while (m--) {
        int c; scanf ("%d", &c);
        if (c == 2) {
            int pos; scanf ("%d", &pos);
            printf ("%I64d\n", get(1, 1, (int)1e6, pos));
        } else {
            int pos, he; scanf ("%d %d", &pos, &he);
            if (pos > 1) {
                up(1, min(a[pos], a[pos - 1]), max(a[pos], a[pos - 1]), 1, (int)1e6, -1);
                up(1, min(he, a[pos - 1]), max(he, a[pos - 1]), 1, (int)1e6, 1);
            }
            if (pos < n) {
                up(1, min(a[pos], a[pos + 1]), max(a[pos], a[pos + 1]), 1, (int)1e6, -1);
                up(1, min(he, a[pos + 1]), max(he, a[pos + 1]), 1, (int)1e6, 1);
            }
            a[pos] = he;
        }
    }
}

Compilation message (stderr)

game.cpp:62:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
game.cpp: In function 'int main()':
game.cpp:76:56: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll {aka long long int}' [-Wformat=]
             printf ("%I64d\n", get(1, 1, (int)1e6, pos));
                                                        ^
game.cpp:63:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int n, m; scanf ("%d %d", &n, &m);
                                      ^
game.cpp:66:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%lld", a + i);
                              ^
game.cpp:73:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int c; scanf ("%d", &c);
                                ^
game.cpp:75:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             int pos; scanf ("%d", &pos);
                                        ^
game.cpp:78:52: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             int pos, he; scanf ("%d %d", &pos, &he);
                                                    ^

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