Submission #958223

#	Time	Username	Problem	Language	Result	Execution time	Memory
958223		Pring	Seats (IOI18_seats)	C++17	100 / 100	2075 ms	259156 KiB

seats

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

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

// #define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

namespace {
    pli operator+(pli a, pli b) {
        if (a.fs < b.fs) return a;
        if (a.fs > b.fs) return b;
        return mp(a.fs, a.sc + b.sc);
    }
    const int MXN = 3000039, INF = 2e9;
    int n, h, w;
    pii pos[MXN];
    int time[MXN];

    struct SMG {
        #define mid ((l + r) >> 1)
        pli val[MXN * 4];
        ll tag[MXN * 4];
        void add_tag(int id, int l, int r, ll _t) {
            val[id].fs += _t;
            tag[id] += _t;
        }
        void push(int id, int l, int r) {
            if (tag[id] == 0) return;
            add_tag(id * 2 + 1, l, mid, tag[id]);
            add_tag(id * 2 + 2, mid, r, tag[id]);
            tag[id] = 0;
        }
        void pull(int id, int l, int r) {
            val[id] = val[id * 2 + 1] + val[id * 2 + 2];
        }
        void build(int id, int l, int r) {
            tag[id] = 0;
            if (l + 1 == r) {
                val[id] = mp(0LL, 1);
                return;
            }
            build(id * 2 + 1, l, mid);
            build(id * 2 + 2, mid, r);
            pull(id, l, r);
        }
        void modify(int id, int l, int r, int _l, int _r, int _v) {
            if (_r <= l || r <= _l) return;
            if (_l <= l && r <= _r) {
                add_tag(id, l, r, _v);
                return;
            }
            push(id, l, r);
            modify(id * 2 + 1, l, mid, _l, _r, _v);
            modify(id * 2 + 2, mid, r, _l, _r, _v);
            pull(id, l, r);
        }
        #undef mid
    } smg;

    int f(int x, int y) {
        return x * (w + 2) + y;
    }

    int f(pii p) {
        return p.fs * (w + 2) + p.sc;
    }

    void MODIFY(int x, int y, int mul) {
        int a = time[f(x, y)];
        int b = time[f(x, y + 1)];
        int c = time[f(x + 1, y)];
        int d = time[f(x + 1, y + 1)];
        if (d < c) swap(d, c);
        if (c < b) swap(c, b);
        if (b < a) swap(b, a);
        if (d < c) swap(d, c);
        if (c < b) swap(c, b);
        if (d < c) swap(d, c);
        // debug(x, y, a, b, c, d);
        if (a < b) smg.modify(0, 0, n, a, b, mul);
        if (c < d) smg.modify(0, 0, n, c, d, INF * mul);
        // auto [sml, cnt] = smg.val[0];
        // debug(sml, cnt);
    }

    void INIT() {
        FOR(i, 0, n) time[f(pos[i])] = i;
        fill(time, time + w + 2, n);
        fill(time + (w + 2) * (h + 1), time + (w + 2) * (h + 2), n);
        FOR(i, 1, h + 1) {
            time[f(i, 0)] = n;
            time[f(i, w + 1)] = n;
        }
        smg.build(0, 0, n);
        // auto [sml, cnt] = smg.val[0];
        // debug(sml, cnt);
        FOR(i, 0, h + 1) FOR(j, 0, w + 1) MODIFY(i, j, 1);
    }

    void UPD(pii p, int x) {
        MODIFY(p.fs - 1, p.sc - 1, -1);
        MODIFY(p.fs - 1, p.sc, -1);
        MODIFY(p.fs, p.sc - 1, -1);
        MODIFY(p.fs, p.sc, -1);
        time[f(p)] = x;
        MODIFY(p.fs - 1, p.sc - 1, 1);
        MODIFY(p.fs - 1, p.sc, 1);
        MODIFY(p.fs, p.sc - 1, 1);
        MODIFY(p.fs, p.sc, 1);
    }

    int CALC(int x, int y) {
        // debug(x, y);
        UPD(pos[x], y);
        UPD(pos[y], x);
        swap(pos[x], pos[y]);
        auto [sml, cnt] = smg.val[0];
        // debug(sml, cnt);
        return (sml == 4 ? cnt : 0);
    }
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    ::h = H;
    ::w = W;
    ::n = h * w;
    FOR(i, 0, h * w) pos[i] = mp(R[i] + 1, C[i] + 1);
    INIT();
}

int swap_seats(int a, int b) {
    return CALC(a, b);
}

// #ifdef MIKU
// void miku() {
// }

// int32_t main() {
//     cin.tie(0) -> sync_with_stdio(false);
//     cin.exceptions(cin.failbit);
//     miku();
//     return 0;
// }
// #endif

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