Submission #1184891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184891		nagorn_ph	Simple game (IZhO17_game)	C++20	100 / 100	225 ms	34632 KiB

game

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

using namespace std;
using namespace __gnu_pbds;

#define ordered_set <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update>

#define int long long
#define double long double
#define pii pair <int, int>
#define tiii tuple <int, int, int>
#define emb emplace_back
#define all(a) a.begin(), a.end()
#define iShowSpeed cin.tie(NULL)->sync_with_stdio(false)

const int mod = 1e9 + 7;
const int inf = 1e18;
const int N = 1e5 + 5;
const int H = 1e6 + 5;

int n, q, a[N];

struct {
    int seg[4 * H], lazy[4 * H];
    void push(int l, int r, int i){
        if (l == r) return;
        lazy[2 * i] += lazy[i];
        lazy[2 * i + 1] += lazy[i];
        seg[2 * i] += lazy[i];
        seg[2 * i + 1] += lazy[i];
        lazy[i] = 0;
    }
    void update(int l, int r, int i, int ll, int rr, int val){
        push(l, r, i);
        if (r < ll || l > rr) return;
        if (l >= ll && r <= rr) {
            seg[i] += val;
            lazy[i] += val;
            push(l, r, i);
            return;
        }
        int mid = (l + r) / 2;
        update(l, mid, 2 * i, ll, rr, val), update(mid + 1, r, 2 * i + 1, ll, rr, val);
    }
    int query(int l, int r, int i, int ll, int rr){
        push(l, r, i);
        if (r < ll || l > rr) return 0;
        if (l >= ll && r <= rr) return seg[i];
        int mid = (l + r) / 2;
        return query(l, mid, 2 * i, ll, rr) + query(mid + 1, r, 2 * i + 1, ll, rr);
    }
} segtree;

int32_t main(){
    iShowSpeed;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (i > 1) segtree.update(1, H, 1, min(a[i - 1], a[i]), max(a[i - 1], a[i]), 1);
    }
    // for (int i = 1; i <= 5; i++) {
    //     cout << segtree.query(1, H, 1, i) << ' ';
    // }
    // cout << "\n";
    while (q--) {
        int op; cin >> op;
        if (op == 1) {
            int idx, val; cin >> idx >> val;
            if (idx > 1) segtree.update(1, H, 1, min(a[idx - 1], a[idx]), max(a[idx - 1], a[idx]), -1);
            if (idx < n) segtree.update(1, H, 1, min(a[idx + 1], a[idx]), max(a[idx + 1], a[idx]), -1);
            a[idx] = val;
            if (idx > 1) segtree.update(1, H, 1, min(a[idx - 1], a[idx]), max(a[idx - 1], a[idx]), 1);
            if (idx < n) segtree.update(1, H, 1, min(a[idx + 1], a[idx]), max(a[idx + 1], a[idx]), 1);
        }
        else {
            int x; cin >> x;
            cout << segtree.query(1, H, 1, x, x) << '\n';
        }
    }
}

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