Submission #1135718

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135718		TAFH	Simple game (IZhO17_game)	C++20	100 / 100	236 ms	34632 KiB

game

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

// #pragma GCC optimize ("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;
// using namespace __gnu_pbds;

#define forn(i, n) for (int i = 0; i < n; i++)
#define ull unsigned long long
#define ll long long
#define int long long
#define SPEED                         \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0)

// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = 4e5 + 13;
const int maxa = 2e5 + 13;
const ll mod = 998244353;
const int mxn = 1e6 + 13;
const int mxa = 1e6 + 13;

void prestart() {}

int t[4 * mxa], dt[4 * mxa];

void push(int v) {
    dt[2 * v] += dt[v];
    dt[2 * v + 1] += dt[v];
    dt[v] = 0; 
}

void update(int v, int l, int r, int tl, int tr, int dv) {
    int mid = (l + r) / 2;
    if (tr < l || r < tl) return;

    if (tl <= l && r <= tr) {
        dt[v] += dv;
        t[v] += dt[v];
        if (l != r) push(v);
        dt[v] = 0;
        return;
    }
        
    t[v] += dt[v];
    if (l != r) push(v);
    dt[v] = 0;

    update(2 * v, l, mid, tl, tr, dv);
    update(2 * v + 1, mid + 1, r, tl, tr, dv);

    t[v] = t[2 * v] + t[2 * v + 1];
}

int get_i(int v, int l, int r, int idx) {
    int mid = (l + r) / 2;
    if (idx < l || r < idx) return -1;

    if (l == r && l == idx) {
        t[v] += dt[v];
        dt[v] = 0;
        return t[v];
    }

    t[v] += dt[v];
    if (l != r) push(v);
    dt[v] = 0;

    return max(get_i(2 * v, l, mid, idx), get_i(2 * v + 1, mid + 1, r, idx));
}

void start() {
    int n, m;
    cin >> n >> m;

    int h[n + 1];
    forn(i, n) cin >> h[i + 1];

    for(int i = 2; i <= n; i++) {
        update(1, 1, mxa, min(h[i - 1], h[i]), max(h[i - 1], h[i]), 1);
    }

    for(int i = 0; i < m; i++) {
        int t;
        cin >> t;
        if (t == 1) {
            int p, v;
            cin >> p >> v;
            if (p > 1) {
                update(1, 1, mxa, min(h[p - 1], h[p]), max(h[p - 1], h[p]), -1);
                update(1, 1, mxa, min(h[p - 1], v), max(h[p - 1], v), 1);
            }
            if (p < n) {
                update(1, 1, mxa, min(h[p + 1], h[p]), max(h[p + 1], h[p]), -1);
                update(1, 1, mxa, min(h[p + 1], v), max(h[p + 1], v), 1);
            }
            h[p] = v;
        }
        else {
            int h;
            cin >> h;
            cout << get_i(1, 1, mxa, h) << "\n";
        }
    }
}


signed main()
{
    SPEED;
    int t = 1;
    prestart();
    // cin >> t;
    while (t--)
    {
        start();
    }
}

• Subtask 1: 22 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51