Submission #1118593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118593		patgra	Seats (IOI18_seats)	C++17	100 / 100	1863 ms	118852 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : c)

#define ll long long

constexpr bool dbg = false;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

using namespace std;

constexpr int treeBase = 1 << 20, maxn = 1e6 + 7, inf = 5;
int n;
int h, w;
vector<vector<int>> arr;
pair<int, int> location[maxn];
int treeMin[2 * treeBase], treeCnt[2 * treeBase], lazy[2 * treeBase];

static inline void fixNode(int v) {
    treeMin[v] = min(treeMin[2 * v] + lazy[2 * v], treeMin[2 * v + 1] + lazy[2 * v + 1]);
    treeCnt[v] = 0;
    if (treeMin[v] == treeMin[2 * v] + lazy[2 * v]) treeCnt[v] += treeCnt[2 * v];
    if (treeMin[v] == treeMin[2 * v + 1] + lazy[2 * v + 1]) treeCnt[v] += treeCnt[2 * v + 1];
}
void initTree() {
    rep(i, 0, treeBase) treeMin[i + treeBase] = inf, treeCnt[i + treeBase] = 1;
    rep(i, 0, n) treeMin[i + treeBase] = 0;
    repD(i, treeBase - 1, -1) fixNode(i);
}

void add(int l, int r, int x) {
    DC << "add " << l << ' ' << r << " + " << x << eol;
    l += treeBase; r += treeBase;
    lazy[l] += x;
    if (l != r) lazy[r] += x;
    while (l / 2 != r / 2) {
        if (l % 2 == 0) lazy[l + 1] += x;
        if (r % 2 == 1) lazy[r - 1] += x;
        l /= 2; r /= 2;
        fixNode(l); fixNode(r);
    }
    l /= 2; r /= 2;
    while (l) fixNode(l), l /= 2;
}
int query() {
    return (treeMin[1] == 4 ? treeCnt[1] : 0);
}

void processCorner(int r, int c, bool remove) {
    vector<int> v; v.reserve(4);
    rep(i, 0, 2) rep(j, 0, 2) v.push_back(arr[r + i][c + j]);
    sort(v.begin(), v.end());
    add(v[0], v[1] - 1, 1 * (remove ? -1 : 1));
    if (v[2] != v[3]) add(v[2], v[3] - 1, inf * (remove ? -1 : 1));
}
void processCorners(int r, int c, bool remove) {
    rep(dr, -1, 1) rep(dc, -1, 1) {
        if (r + dr < 0 || r + dr + 1 >= h + 2 || c + dc < 0 || c + dc + 1 >= w + 2) continue;
        processCorner(r + dr, c + dc, remove);
    }
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    h = H, w = W, n = h * w;
    initTree();
    arr.resize(h + 2); repIn(i, arr) i.resize(w + 2);
    rep(i, 0, n) location[i] = {R[i] + 1, C[i] + 1}, arr[R[i] + 1][C[i] + 1] = i;
    rep(i, 0, h + 2) arr[i][0] = arr[i][w + 1] = n + 1;
    rep(i, 0, w + 2) arr[0][i] = arr[h + 1][i] = n + 1;
    rep(i, 0, h + 1) rep(j, 0, w + 1) processCorner(i, j, false);
    DC << ' ' << query() << eol;
}

int swap_seats(int a, int b) {
    auto& [ra, ca] = location[a];
    auto& [rb, cb] = location[b];
    processCorners(ra, ca, true), processCorners(rb, cb, true);
    swap(ra, rb); swap(ca, cb), swap(arr[ra][ca], arr[rb][cb]);
    processCorners(ra, ca, false), processCorners(rb, cb, false);
    return query();
}

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