제출 #1085601

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1085601		coolboy19521	Simple game (IZhO17_game)	C++17	100 / 100	310 ms	22960 KiB

game

#include "bits/stdc++.h"
#define ll long long

using namespace std;

const int sz = 2e6 + 2;

int st[sz * 4], lz[sz * 4];
int ln, n;

void relax(int v, int lo, int hi) {
    st[v] += lz[v];
    if (lo != hi) {
        lz[v * 2] += lz[v];
        lz[v * 2 + 1] += lz[v];
    }
    lz[v] = 0;
}

void upd(int lo, int hi, int ql, int qr, int v, int k) {
    relax(v, lo, hi);
    if (lo > qr or ql > hi)
        return;
    if (ql <= lo and hi <= qr) {
        lz[v] += k;
        relax(v, lo, hi);
    } else {
        int mi = (lo + hi) / 2;
        upd(lo, mi, ql, qr, v * 2, k);
        upd(mi + 1, hi, ql, qr, v * 2 + 1, k);
    }
}

int qry(int ix) {
    int lo = 1, hi = ln, v = 1;
    while (lo != hi) {
        relax(v, lo, hi);
        int mi = (lo + hi) / 2;
        if (mi >= ix)
            hi = mi, v *= 2;
        else lo = mi + 1, v = v * 2 + 1;
    }
    relax(v, lo, hi);
    return st[v];
}

int a[sz];

void cng(int v, int k) {
    if (n + 1 == v) return;
    if (1 != v and 1 < abs(a[v - 1] - a[v])) {
        int c = min(a[v - 1], a[v]) + 1;
        int d = max(a[v - 1], a[v]) - 1;
        upd(1, ln, c, d, 1, k);
    }
}

int main() {
    int m; cin >> n >> m;
    ln = 1e6 + 5;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i]; cng(i, 1);
    }
    while (m --) {
        int t; cin >> t;
        if (1 == t) {
            int p, v; cin >> p >> v;
            cng(p, -1); cng(p + 1, -1);
            a[p] = v;
            cng(p, 1); cng(p + 1, 1);
        } else {
            int x; cin >> x;
            cout << qry(x) << '\n';
        }
    }
}

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