제출 #515239

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
515239		Mazaalai	Simple game (IZhO17_game)	C++17	100 / 100	323 ms	19508 KiB

game

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
const int M = 4*N;
int n, m;
int node[M], lazy[M], nums[N];
void propagate(int head) {
    if (lazy[head] == 0) return;
    int val = lazy[head];
    lazy[head] = 0;
    node[head*2+1] += val;
    lazy[head*2+1] += val;
    node[head*2+2] += val;
    lazy[head*2+2] += val;
}
void update(int l, int r, int L, int R, int val, int head) {
    if (l > R || L > r) return;
    if (L <= l && r <= R) {
        node[head] += val;
        lazy[head] += val;
        return;
    }
    propagate(head);
    int mid = (l+r)>>1;
    update(l, mid, L, R, val, head*2+1);
    update(mid+1, r, L, R, val, head*2+2);
    node[head] = node[head*2+1] + node[head*2+2];
}
int query(int l, int r, int id, int head) {
    if (l == r) return node[head];
    propagate(head);
    int mid = (l+r)>>1;
    if (id <= mid) return query(l, mid, id, head*2+1);
    return query(mid+1, r, id, head*2+2);
}
signed main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> nums[i];
    for (int i = 2; i <= n; i++) {
        int st = nums[i-1], end = nums[i];
        if (st > end) swap(st, end);
        if (st != end) update(0, N, st+1, end-1, 1, 0);
    }
    // for (int j = 1; j <= 10; j++) cout << query(0, N, j, 0) << " \n"[j==10];
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a;
        if (a == 1) {
            cin >> a >> b;
            if (a - 1 > 0) {
                int st = nums[a-1], end = nums[a];
                if (st > end) swap(st, end);
                if (st != end) update(0, N, st+1, end-1, -1, 0);
            }
            if (a + 1 <= n) {
                int st = nums[a], end = nums[a+1];
                if (st > end) swap(st, end);
                if (st != end) update(0, N, st+1, end-1, -1, 0);
            }
            nums[a] = b;
            if (a - 1 > 0) {
                int st = nums[a-1], end = nums[a];
                if (st > end) swap(st, end);
                if (st != end) update(0, N, st+1, end-1, 1, 0);
            }
            if (a + 1 <= n) {
                int st = nums[a], end = nums[a+1];
                if (st > end) swap(st, end);
                if (st != end) update(0, N, st+1, end-1, 1, 0);
            }
            // for (int j = 1; j <= 10; j++) cout << query(0, N, j, 0) << " \n"[j==10];
        } else {
            cin >> a;
            cout << query(0, N, a, 0) << '\n';
        }
    }
}

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