oj.uz

Submission #854559

# Submission time Handle Problem Language Result Execution time Memory
854559 2023-09-28T04:16:11 Z The_Samurai Simple game (IZhO17_game) C++17
22 / 100
 1000 ms 1344 KB 
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int inf = 1e9;

struct Fenwick {
    vector<int> tree;
    int len;

    void init(int n) {
        len = n;
        tree.assign(len + 1, 0);
    }

    void update(int i, int v) {
        i++;
        while (i <= len) {
            tree[i] += v;
            i += i & (-i);
        }
    }

    int get(int i) {
        i++;
        int sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= i & (-i);
        }
    }

    int get(int l, int r) {
        return get(r) - get(l - 1);
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(false);
#ifdef sunnatov
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
//    freopen("subsequence.in", "r", stdin);
//    freopen("subsequence.out", "w", stdout);
#endif

    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int i, v;
            cin >> i >> v;
            a[i] = v;
        } else {
            int h, ans = 0;
            cin >> h;
            for (int i = 1; i <= n; i++) assert(a[i] != h);
            for (int i = 2; i <= n; i++) {
                ans += a[i - 1] < h and h < a[i] or a[i] < h and h < a[i - 1];
            }
            cout << ans << '\n';
        }
    }
}

Compilation message

game.cpp: In member function 'int Fenwick::get(int)':
game.cpp:30:5: warning: no return statement in function returning non-void [-Wreturn-type]
   30 |     }
      |     ^
game.cpp: In function 'int main()':
game.cpp:63:37: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   63 |                 ans += a[i - 1] < h and h < a[i] or a[i] < h and h < a[i - 1];

Subtask #1
22.0 / 22.0

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

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 360 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Execution timed out 1080 ms 1344 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 360 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Execution timed out 1080 ms 1344 KB Time limit exceeded
9 Halted 0 ms 0 KB -