Submission #1305357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305357		LucasLe	Simple game (IZhO17_game)	C++20	100 / 100	199 ms	44392 KiB

game

#include <bits/stdc++.h>

const int maxn = 1e5 + 5;
const int maxx = 1e6 + 5;

int N, M;
int h[maxn + 5];
bool vis[maxn + 5];
std::vector<int> g[maxx + 5];
int info[4 * maxx + 5], tag[4 * maxx + 5];

void update(int id, int l, int r, int pos, int val) {
    if (l == r) {
        info[id] = val;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid)
        update(id << 1, l, mid, pos, val);
    else
        update(id << 1 | 1, mid + 1, r, pos, val);
}

void push(int id) {
    tag[id << 1] += tag[id];
    tag[id << 1 | 1] += tag[id];
    info[id << 1] += tag[id];
    info[id << 1 | 1] += tag[id];
    tag[id] = 0;
}

void update_range(int id, int l, int r, int lb, int rb, int val) {
    if  (lb <= l && r <= rb) {
        tag[id] += val;
        info[id] += val;
        return;
    }
    int mid = (l + r) >> 1;
    push(id);
    if (lb <= mid)
        update_range(id << 1, l, mid, lb, rb, val);
    if (rb > mid)
        update_range(id << 1 | 1, mid + 1, r, lb, rb, val);
}

int get(int id, int l, int r, int pos) {
    if (l == r) {
        return info[id];
    }
    push(id);
    int mid = (l + r) >> 1;
    if (pos <= mid)
        return get(id << 1, l, mid, pos);
    else
        return get(id << 1 | 1, mid + 1, r, pos);
}

void update(int pos, int val) {
    update(1, 1, maxx, pos, val);
}

void update_range(int l, int r, int val) {
    update_range(1, 1, maxx, l, r, val);
}

int get(int pos) {
    return get(1, 1, maxx, pos);
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0);

    std::cin >> N >> M;
    for (int i = 1; i <= N; ++i) {
        std::cin >> h[i];
        g[h[i]].push_back(i);
    }

    // If a point has the same height as the line, we consider that point to have lower height than the line
    for (int i = 1, val, cur = 0, mn = N + 1, mx = 0, cntcomp = 0; i <= maxx; ++i) {
        for (int x : g[i]) {
            vis[x] = true;
            mn = std::min(mn, x);
            mx = std::max(mx, x);
            if (!vis[x - 1] && !vis[x + 1]) cntcomp++;
            else if (vis[x - 1] && vis[x + 1]) cntcomp--;
        }
        if (mn != N + 1) {
            val = (cntcomp - 1) * 2 + 2;
            val -= (mn == 1);
            val -= (mx == N);
        } else {
            val = 0;
        }
        update(i, val);
    }

    while (M--) {
        int type; std::cin >> type;
        if (type == 1) {
            int pos, y; std::cin >> pos >> y;
            int &x = h[pos], bound;
            if (x < y) {

                if (pos != 1) {
                    bound = std::min(y, h[pos - 1]) - 1;
                    if (bound >= x) 
                        update_range(x, bound, -1);
                    bound = std::max(x, h[pos - 1]);
                    if (bound < y)
                        update_range(bound, y - 1, +1);
                }
                if (pos != N) {
                    bound = std::min(y, h[pos + 1]) - 1;
                    if (bound >= x) 
                        update_range(x, bound, -1);
                    bound = std::max(x, h[pos + 1]);
                    if (bound < y)
                        update_range(bound, y - 1, +1);
                }

                // >= h[pos - 1]
                // >= x
                // < y

                // < y
                // < h[pos - 1]
                // >= x
            } else {

                if (pos != 1) {
                    bound = std::max(y, h[pos - 1]);
                    if (bound < x) 
                        update_range(bound, x - 1, -1);
                    bound = std::min(h[pos - 1], x) - 1;
                    if (y <= bound)
                        update_range(y, bound, +1);
                }
                if (pos != N) {
                    bound = std::max(y, h[pos + 1]);
                    if (bound < x) 
                        update_range(bound, x - 1, -1);
                    bound = std::min(h[pos + 1], x) - 1;
                    if (y <= bound)
                        update_range(y, bound, +1);
                }

                // < h[pos - 1]
                // < x
                // >= y

                // < x
                // >= y
                // >= h[pos - 1]
            }
            x = y;
        } else {
            int H; std::cin >> H;
            std::cout << get(H) << '\n';
        }
    }

    return 0;
}

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