oj.uz

Submission #731845

# Submission time Handle Problem Language Result Execution time Memory
731845 2023-04-28T05:16:15 Z stevancv Simple game (IZhO17_game) C++14
100 / 100
 320 ms 19460 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e6 + 2;
const int inf = 2e9 + 2;
int st[4 * N], lzy[4 * N];
void Propagate(int node, int l, int r) {
    if (lzy[node] == 0) return;
    if (l < r) {
        lzy[2 * node] += lzy[node];
        lzy[2 * node + 1] += lzy[node];
    }
    st[node] += lzy[node];
    lzy[node] = 0;
}
void Add(int node, int l, int r, int ql, int qr, int x) {
    Propagate(node, l, r);
    if (r < ql || qr < l || ql > qr) return;
    if (ql <= l && r <= qr) {
        lzy[node] += x;
        Propagate(node, l, r);
        return;
    }
    int mid = l + r >> 1;
    Add(2 * node, l, mid, ql, qr, x);
    Add(2 * node + 1, mid + 1, r, ql, qr, x);
    st[node] = max(st[2 * node], st[2 * node + 1]);
}
int Get(int node, int l, int r, int x) {
    Propagate(node, l, r);
    if (l == r) return st[node];
    int mid = l + r >> 1;
    if (x <= mid) return Get(2 * node, l, mid, x);
    return Get(2 * node + 1, mid + 1, r, x);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i < n; i++) {
        int manji = min(a[i - 1], a[i]);
        int veci = max(a[i - 1], a[i]);
        Add(1, 1, N, manji + 1, veci - 1, 1);
    }
    while (q--) {
        int ty; cin >> ty;
        if (ty == 2) {
            int x; cin >> x;
            cout << Get(1, 1, N, x) << en;
            continue;
        }
        int i, manji, veci; cin >> i; i -= 1;
        if (i > 0) {
            manji = min(a[i - 1], a[i]);
            veci = max(a[i - 1], a[i]);
            Add(1, 1, N, manji + 1, veci - 1, -1);
        }
        if (i < n - 1) {
            manji = min(a[i], a[i + 1]);
            veci = max(a[i], a[i + 1]);
            Add(1, 1, N, manji + 1, veci - 1, -1);
        }
        cin >> a[i];
        if (i > 0) {
            manji = min(a[i - 1], a[i]);
            veci = max(a[i - 1], a[i]);
            Add(1, 1, N, manji + 1, veci - 1, 1);
        }
        if (i < n - 1) {
            manji = min(a[i], a[i + 1]);
            veci = max(a[i], a[i + 1]);
            Add(1, 1, N, manji + 1, veci - 1, 1);
        }
    }
    return 0;
}

Compilation message

game.cpp: In function 'void Add(int, int, int, int, int, int)':
game.cpp:29:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     int mid = l + r >> 1;
      |               ~~^~~
game.cpp: In function 'int Get(int, int, int, int)':
game.cpp:37:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 10 ms 15060 KB Output is correct
3 Correct 9 ms 14684 KB Output is correct
4 Correct 9 ms 15064 KB Output is correct
5 Correct 13 ms 14932 KB Output is correct
6 Correct 10 ms 14808 KB Output is correct
7 Correct 7 ms 12756 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 10 ms 15060 KB Output is correct
3 Correct 9 ms 14684 KB Output is correct
4 Correct 9 ms 15064 KB Output is correct
5 Correct 13 ms 14932 KB Output is correct
6 Correct 10 ms 14808 KB Output is correct
7 Correct 7 ms 12756 KB Output is correct
8 Correct 54 ms 1800 KB Output is correct
9 Correct 141 ms 19280 KB Output is correct
10 Correct 151 ms 19272 KB Output is correct
11 Correct 28 ms 1576 KB Output is correct
12 Correct 93 ms 3296 KB Output is correct
13 Correct 111 ms 19128 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 10 ms 15060 KB Output is correct
3 Correct 9 ms 14684 KB Output is correct
4 Correct 9 ms 15064 KB Output is correct
5 Correct 13 ms 14932 KB Output is correct
6 Correct 10 ms 14808 KB Output is correct
7 Correct 7 ms 12756 KB Output is correct
8 Correct 54 ms 1800 KB Output is correct
9 Correct 141 ms 19280 KB Output is correct
10 Correct 151 ms 19272 KB Output is correct
11 Correct 28 ms 1576 KB Output is correct
12 Correct 93 ms 3296 KB Output is correct
13 Correct 111 ms 19128 KB Output is correct
14 Correct 301 ms 19460 KB Output is correct
15 Correct 294 ms 19252 KB Output is correct
16 Correct 303 ms 19280 KB Output is correct
17 Correct 320 ms 19340 KB Output is correct
18 Correct 307 ms 19276 KB Output is correct