Submission #758109

#	Time	Username	Problem	Language	Result	Execution time	Memory
758109		vjudge1	Simple game (IZhO17_game)	C++17	100 / 100	346 ms	32984 KiB

game

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int mxN = 1e6 + 7;
const int SZ = exp2(ceil(log2(mxN)));

int arr[mxN], seg[2 * SZ], lazy[2 * SZ];

void push(int ind, int l, int r) {
    seg[ind] += (r - l + 1) * lazy[ind];
    if (l != r) {
        lazy[2 * ind] += lazy[ind];
        lazy[2 * ind + 1] += lazy[ind];
    }
    lazy[ind] = 0;
}

void update(int lo, int hi, int val, int ind = 1, int l = 1, int r = SZ) {
    push(ind, l, r);
    if (hi < l || lo > r) {
        return;
    }

    if (lo <= l && r <= hi) {
        lazy[ind] += val;
        push(ind, l, r);
        return;
    }

    int mid = (l + r) / 2;
    update(lo, hi, val, 2 * ind, l, mid);
    update(lo, hi, val, 2 * ind + 1, mid + 1, r);

    seg[ind] = seg[2 * ind] + seg[2 * ind] + 1;
}

int query(int pos, int ind = 1, int l = 1, int r = SZ) {
    push(ind, l, r);
    if (l == r) {
        return seg[ind];
    }

    int mid = (l + r) / 2;
    if (pos <= mid) {
        return query(pos, 2 * ind, l, mid);
    }
    else {
        return query(pos, 2 * ind + 1, mid + 1, r);
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < n; ++i) {
        cin >> arr[i];

        if (i) {
            update(min(arr[i - 1], arr[i]), max(arr[i - 1], arr[i]), 1);
        }
    }

    while (m--) {
        int t;
        cin >> t;
        
        if (t == 1) {
            int pos, val;
            cin >> pos >> val;
            --pos;
            
            if (pos) {
                update(min(arr[pos - 1], arr[pos]), max(arr[pos - 1], arr[pos]), -1);
            }
            if (pos < n - 1) {
                update(min(arr[pos + 1], arr[pos]), max(arr[pos + 1], arr[pos]), -1);
            }
            arr[pos] = val;
            if (pos) {
                update(min(arr[pos - 1], arr[pos]), max(arr[pos - 1], arr[pos]), 1);
            }
            if (pos < n - 1) {
                update(min(arr[pos + 1], arr[pos]), max(arr[pos + 1], arr[pos]), 1);
            }
        }
        else {
            int h;
            cin >> h;
            
            cout << query(h) << "\n";
        }
    }
}

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