Submission #682517

#	Time	Username	Problem	Language	Result	Execution time	Memory
682517		opPO	Simple game (IZhO17_game)	C++17	100 / 100	234 ms	19792 KiB

game

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define f first
#define s second
#define pb push_back
#define ld long double
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define vec vector

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
const ld eps = 1e-6;
const int mod = 998244353;
const int oo = 2e9;
const ll OO = 2e18;
const int N = 1e6 + 10;
int sum[4 * N];

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

void upd(int l, int r, int delta, int v, int tl, int tr)
{
    if (tl > r || tr < l) return;
    if (tl >= l && tr <= r)
    {
        sum[v] += delta;
        return;
    }
    push(v);
    int m = (tl + tr) / 2;
    upd(l, r, delta, 2 * v + 1, tl, m);
    upd(l, r, delta, 2 * v + 2, m + 1, tr);
}

int get(int idx, int v, int tl, int tr)
{
    if (tl == tr) return sum[v];
    push(v);
    int m = (tl + tr) / 2;
    if (idx <= m) return get(idx, 2 * v + 1, tl, m);
    else return get(idx, 2 * v + 2, m + 1, tr);
}

void solve()
{
    int n, q;
    cin >> n >> q;
    vec<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i < n; i++)
    {
        int mn = min(a[i], a[i + 1]);
        int mx = a[i] + a[i + 1] - mn;
        upd(mn, mx, +1, 0, 1, N - 1);
    }
    while (q--)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int p, x;
            cin >> p >> x;
            if (p > 1)
            {
                int mn = min(a[p - 1], a[p]);
                int mx = a[p - 1] + a[p] - mn;
                upd(mn, mx, -1, 0, 1, N - 1);
            }
            if (p < n)
            {
                int mn = min(a[p], a[p + 1]);
                int mx = a[p] + a[p + 1] - mn;
                upd(mn, mx, -1, 0, 1, N - 1);
            }
            a[p] = x;
            if (p > 1)
            {
                int mn = min(a[p - 1], a[p]);
                int mx = a[p - 1] + a[p] - mn;
                upd(mn, mx, +1, 0, 1, N - 1);
            }
            if (p < n)
            {
                int mn = min(a[p], a[p + 1]);
                int mx = a[p] + a[p + 1] - mn;
                upd(mn, mx, +1, 0, 1, N - 1);
            }
        }
        else
        {
            int h;
            cin >> h;
            cout << get(h, 0, 1, N - 1) << "\n";
        }
    }
}

int32_t main()
{
//    freopen("game.in", "r", stdin);
//    freopen("game.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

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