oj.uz

Submission #38357

# Submission time Handle Problem Language Result Execution time Memory
38357 2018-01-04T03:49:19 Z Just_Solve_The_Problem Simple game (IZhO17_game) C++11
100 / 100
 436 ms 71424 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 71424 KB Output is correct
2 Correct 3 ms 71424 KB Output is correct
3 Correct 0 ms 71424 KB Output is correct
4 Correct 0 ms 71424 KB Output is correct
5 Correct 3 ms 71424 KB Output is correct
6 Correct 0 ms 71424 KB Output is correct
7 Correct 3 ms 71424 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 71424 KB Output is correct
2 Correct 3 ms 71424 KB Output is correct
3 Correct 0 ms 71424 KB Output is correct
4 Correct 0 ms 71424 KB Output is correct
5 Correct 3 ms 71424 KB Output is correct
6 Correct 0 ms 71424 KB Output is correct
7 Correct 3 ms 71424 KB Output is correct
8 Correct 113 ms 71424 KB Output is correct
9 Correct 193 ms 71424 KB Output is correct
10 Correct 196 ms 71424 KB Output is correct
11 Correct 96 ms 71424 KB Output is correct
12 Correct 156 ms 71424 KB Output is correct
13 Correct 149 ms 71424 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 71424 KB Output is correct
2 Correct 3 ms 71424 KB Output is correct
3 Correct 0 ms 71424 KB Output is correct
4 Correct 0 ms 71424 KB Output is correct
5 Correct 3 ms 71424 KB Output is correct
6 Correct 0 ms 71424 KB Output is correct
7 Correct 3 ms 71424 KB Output is correct
8 Correct 113 ms 71424 KB Output is correct
9 Correct 193 ms 71424 KB Output is correct
10 Correct 196 ms 71424 KB Output is correct
11 Correct 96 ms 71424 KB Output is correct
12 Correct 156 ms 71424 KB Output is correct
13 Correct 149 ms 71424 KB Output is correct
14 Correct 399 ms 71424 KB Output is correct
15 Correct 359 ms 71424 KB Output is correct
16 Correct 369 ms 71424 KB Output is correct
17 Correct 436 ms 71424 KB Output is correct
18 Correct 399 ms 71424 KB Output is correct