Submission #464281

#	Time	Username	Problem	Language	Result	Execution time	Memory
464281		TeaTime	Simple game (IZhO17_game)	C++17	100 / 100	232 ms	19780 KiB

game

//#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 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51