Submission #137188

#	Time	Username	Problem	Language	Result	Execution time	Memory
137188		meatrow	Simple game (IZhO17_game)	C++17	100 / 100	219 ms	11340 KiB

game

#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
//#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

const int N = 1e6 + 5;

int t[N * 4];

void update(int v, int tl, int tr, int l, int r, int add) {
    if (l > r)
        return;
    if (l == tl && r == tr) {
        t[v] += add;
    } else {
        int tm = (tl + tr) / 2;
        update(v*2, tl, tm, l, min(r, tm), add);
        update(v*2+1, tm+1, tr, max(l, tm+1), r, add);
    }
}

int get(int v, int tl, int tr, int pos) {
    if (tl == tr)
        return t[v];
    int tm = (tl + tr) / 2;
    if (pos <= tm)
        return t[v] + get(v*2, tl, tm, pos);
    else
        return t[v] + get(v*2+1, tm+1, tr, pos);
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
        if (i) {
            update(1, 0, N - 1, min(h[i], h[i - 1]), max(h[i], h[i - 1]), 1);
        }
    }
    while (m--) {
        int type;
        cin >> type;
        if (type == 1) {
            int i, val;
            cin >> i >> val;
            i--;
            if (i) {
                update(1, 0, N - 1, min(h[i], h[i - 1]), max(h[i], h[i - 1]), -1);
            }
            if (i + 1 < n) {
                update(1, 0, N - 1, min(h[i], h[i + 1]), max(h[i], h[i + 1]), -1);
            }
            h[i] = val;
            if (i) {
                update(1, 0, N - 1, min(h[i], h[i - 1]), max(h[i], h[i - 1]), 1);
            }
            if (i + 1 < n) {
                update(1, 0, N - 1, min(h[i], h[i + 1]), max(h[i], h[i + 1]), 1);
            }
        } else {
            int x;
            cin >> x;
            cout << get(1, 0, N - 1, x) << '\n';
        }
    }
    return 0;
}

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