oj.uz

Submission #464281

# Submission time Handle Problem Language Result Execution time Memory
464281 2021-08-12T17:14:07 Z TeaTime Simple game (IZhO17_game) C++17
100 / 100
 232 ms 19780 KB 
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>

using namespace std;

#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

typedef long long ll;
typedef long double ld;

#define int ll
const ll SZ = 1e6 + 10;
ll n, q;
vector<ll> vec1, vec2;
ll psh[SZ * 8], seg[SZ * 8];

ll get(int v, int l, int r, int pos) {
    if (l == r - 1) {
        return seg[v];
    } else {
        int mid = (l + r) / 2;
        if (pos < mid) {
            return get(v * 2 + 1, l, mid, pos) + seg[v];
        } else {
            return get(v * 2 + 2, mid, r, pos) + seg[v];
        }
    }
}

void upd(int v, int l, int r, int askl, int askr, int dif) {
    if (l >= askr || r <= askl) return;

    if (askl <= l && r <= askr) {
        seg[v] += dif;
        return;
    }

    int mid = (l + r) / 2;
    upd(v * 2 + 1, l, mid, askl, askr, dif);
    upd(v * 2 + 2, mid, r, askl, askr, dif);
}

vector<ll> vec;
void er(int i) {
    if (i == 0) return;
    if (i == n) return;

    ll mn = min(vec[i - 1], vec[i]), mx = max(vec[i - 1], vec[i]);
    upd(0, 0, SZ, mn, mx + 1, -1);
}

void add(int i) {
    if (i == 0) return;
    if (i == n) return;

    ll mn = min(vec[i - 1], vec[i]), mx = max(vec[i - 1], vec[i]);
    upd(0, 0, SZ, mn, mx + 1, 1);
}


signed main() {
    fastInp;

    cin >> n >> q;

    vec.resize(n);
    for (auto& c : vec) cin >> c;

    for (int i = 1; i < n; i++) {
        add(i);
    }
    while (q--) {
        ll t;
        cin >> t;
        if (t == 1) {
            ll pos, val;
            cin >> pos >> val;
            pos--;
            er(pos);
            er(pos + 1);
            vec[pos] = val;
            add(pos);
            add(pos + 1);
        } else {
            ll h;
            cin >> h;
            cout << get(0, 0, SZ, h) << "\n";
        }
    }
    return 0;
}

/*
3 4
RGWR
GRGG
RGWW

4 4
RGWR
GRRG
WGGW
WWWR

5 5
RGRGW
GRRGW
WGGWR
RWRGW
RGWGW
*/

Subtask #1
22.0 / 22.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 6 ms 9420 KB Output is correct
3 Correct 6 ms 9420 KB Output is correct
4 Correct 6 ms 9292 KB Output is correct
5 Correct 7 ms 9420 KB Output is correct
6 Correct 7 ms 9420 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 57 ms 2024 KB Output is correct
9 Correct 135 ms 19684 KB Output is correct
10 Correct 149 ms 19756 KB Output is correct
11 Correct 50 ms 1988 KB Output is correct
12 Correct 89 ms 3556 KB Output is correct
13 Correct 89 ms 3228 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 6 ms 9420 KB Output is correct
3 Correct 6 ms 9420 KB Output is correct
4 Correct 6 ms 9292 KB Output is correct
5 Correct 7 ms 9420 KB Output is correct
6 Correct 7 ms 9420 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 57 ms 2024 KB Output is correct
9 Correct 135 ms 19684 KB Output is correct
10 Correct 149 ms 19756 KB Output is correct
11 Correct 50 ms 1988 KB Output is correct
12 Correct 89 ms 3556 KB Output is correct
13 Correct 89 ms 3228 KB Output is correct
14 Correct 221 ms 19632 KB Output is correct
15 Correct 220 ms 19632 KB Output is correct
16 Correct 213 ms 19652 KB Output is correct
17 Correct 211 ms 19656 KB Output is correct
18 Correct 232 ms 19780 KB Output is correct