Submission #1221624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221624		not_amir	Seats (IOI18_seats)	C++20	100 / 100	2413 ms	211828 KiB

seats

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

typedef pair<int, int> pii;

struct vertex {
    int lv, rv;
    array<int, 2> cnt;
    int convex = 0, corner = 0;
};

constexpr int MAX = 5e6;

vertex st[MAX];
int t = 0;

template<size_t N>
array<int, N> operator+(array<int, N> &f, array<int, N> &s) {
    array<int, N> res;
    for (int i = 0; i < N; i++)
        res[i] = f[i] + s[i];
    return res;
}

int build(int tl, int tr) {
    if (tl + 1 == tr) {
        st[++t].cnt = {1, 0};
        return t;
    }
    int tm = (tl + tr) / 2;
    int v = ++t;
    st[v].lv = build(tl, tm), st[v].rv = build(tm, tr);
    st[v].cnt = st[st[v].lv].cnt + st[st[v].rv].cnt;
    return v;
}

void update(int v, int tl, int tr, int l, int r, int convex, int corner) {
    if (l >= r)
        return;
    if (l == tl && r == tr)
        st[v].convex += convex, st[v].corner += corner;
    else {
        int tm = (tl + tr) / 2;
        update(st[v].lv, tl, tm, l, min(r, tm), convex, corner);
        update(st[v].rv, tm, tr, max(l, tm), r, convex, corner);
    }
    if (tl + 1 == tr)
        st[v].cnt = {1, 0};
    else
        st[v].cnt = st[st[v].lv].cnt + st[st[v].rv].cnt;
    if (st[v].corner == 1) {
        st[v].cnt[1] = st[v].cnt[0];
        st[v].cnt[0] = 0;
    }
    if (st[v].corner > 1 || st[v].convex)
        st[v].cnt = {0, 0};
}

pii convex[MAX], corner[MAX], p_inv[MAX];

vector<vector<int>> B;

int H, W;

int get(int i, int j) {
    if (i < 0 || i >= H || j < 0 || j >= W)
        return H * W;
    return B[i][j];
}

int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

void update(int i, int j, bool s = false) {
    if (i < 0 || i >= H || j < 0 || j >= W)
        return;
    int x = B[i][j];
    if (!s) {
        update(1, 0, H * W, convex[x].first, convex[x].second, -1, 0);
        update(1, 0, H * W, corner[x].first, corner[x].second, 0, -1);
    }
    corner[x] = {x, min(get(i - 1, j), get(i, j - 1))};
    vector<int> val;
    for (int d = 0; d < 4; d++)
        val.push_back(get(i + dx[d], j + dy[d]));
    sort(val.begin(), val.end());
    convex[x] = {val[1], x};
    update(1, 0, H * W, convex[x].first, convex[x].second, 1, 0);
    update(1, 0, H * W, corner[x].first, corner[x].second, 0, 1);
}

void give_initial_chart(int _H, int _W, vector<int> R, vector<int> C) {
    H = _H, W = _W;
    B.resize(H, vector<int>(W));
    for (int i = 0; i < H * W; i++) {
        B[R[i]][C[i]] = i;
        p_inv[i] = {R[i], C[i]};
    }
    build(0, H * W);
    for (int i = 0; i < H; i++)
        for (int j = 0; j < W; j++)
            update(i, j, true);
}

int swap_seats(int a, int b) {
    auto [i1, j1] = p_inv[a];
    auto [i2, j2] = p_inv[b];
    swap(B[i1][j1], B[i2][j2]);
    swap(p_inv[a], p_inv[b]);
    update(i1, j1), update(i2, j2);
    for (int d = 0; d < 4; d++){
        update(i1 + dx[d], j1 + dy[d]);
        update(i2 + dx[d], j2 + dy[d]);
    }
    return st[1].cnt[1];
}

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 20 / 20
• Subtask 4: 6 / 6
• Subtask 5: 33 / 33
• Subtask 6: 30 / 30