oj.uz

Submission #37667

# Submission time Handle Problem Language Result Execution time Memory
37667 2017-12-26T17:29:42 Z adlet Simple game (IZhO17_game) C++14
22 / 100
 219 ms 5540 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
const int INF = 1e9 + 5;

int n, m, pos[N], t[N * 4], z[N * 4];

inline void push(int v, int tl, int tr) {
    if (z[v] != 0) {
        if (tl != tr) {
            t[v * 2] = z[v];
            t[v * 2 + 1] = z[v];
            z[v * 2] = z[v];
            z[v * 2 + 1] = z[v];
        }
        z[v] = 0;
    }
}

inline void upd(int v, int tl, int tr, int l, int r) {
    push(v, tl, tr);
    if (tl > r || tr < l) {
        return;
    }
    if (tl >= l && tr <= r) {
        t[v]++;
        z[v]++;
        push(v, tl, tr);
        return;
    }
    push(v, tl, tr);
    int tm = (tl + tr) / 2;
    upd(v * 2, tl, tm, l, r);
    upd(v * 2 + 1, tm + 1, tr, l, r);
    t[v] = min(t[v * 2], t[v * 2 + 1]);
}

int get(int v, int tl, int tr, int l, int r) {
    push(v, tl, tr);
    if (tl > r || tr < l)
        return INF;
    if (tl >= l && tr <= r)
        return t[v];
    push(v, tl, tr);
    int tm = (tl + tr) / 2;
    return min(get(v * 2, tl, tm, l, r),
               get(v * 2 + 1, tm + 1, tr, l, r));
}

int main() {
//    freopen("game.in", "r", stdin);
//    freopen("game.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> pos[i];
        if (i > 1)
            upd(1, 1, N, min(pos[i], pos[i - 1]) + 1, -1 +  max(pos[i], pos[i - 1]));
    }
    if (m <= 1000 && n <= 1000) {
        for (int i = 1; i <= m; ++i) {
            int type;
            cin >> type;
            if (type == 1) {
                int j, val;
                cin >> j >> val;
                pos[j] = val;
            } else {
                int h, cnt = 0;
                cin >> h;
                for (int j = 1; j < n; ++j) {
                    if ((pos[j] > h && pos[j + 1] < h) || (pos[j] < h && pos[j + 1] > h))
                        ++cnt;
                }
                cout << cnt << "\n";
            }
        }
        return 0;
    }
    for (int i = 1; i <= m; ++i) {
        int type;
        cin >> type;
        if (type == 1) {
            int j, val;
            cin >> j >> val;
            pos[j] = val;
        } else {
            int h, cnt = 0;
            cin >> h;
            cout << get(1, 1, n, h, h) << "\n";
        }
    }
}

Compilation message

game.cpp: In function 'int main()':
game.cpp:89:20: warning: unused variable 'cnt' [-Wunused-variable]
             int h, cnt = 0;
                    ^

Subtask #1
22.0 / 22.0

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

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5540 KB Output is correct
2 Correct 3 ms 5540 KB Output is correct
3 Correct 6 ms 5540 KB Output is correct
4 Correct 6 ms 5540 KB Output is correct
5 Correct 6 ms 5540 KB Output is correct
6 Correct 3 ms 5540 KB Output is correct
7 Correct 3 ms 5540 KB Output is correct
8 Runtime error 219 ms 5540 KB Execution timed out (wall clock limit exceeded)
9 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5540 KB Output is correct
2 Correct 3 ms 5540 KB Output is correct
3 Correct 6 ms 5540 KB Output is correct
4 Correct 6 ms 5540 KB Output is correct
5 Correct 6 ms 5540 KB Output is correct
6 Correct 3 ms 5540 KB Output is correct
7 Correct 3 ms 5540 KB Output is correct
8 Runtime error 219 ms 5540 KB Execution timed out (wall clock limit exceeded)
9 Halted 0 ms 0 KB -