제출 #1018408

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1018408		efishel	자리 배치 (IOI18_seats)	C++17	100 / 100	2617 ms	149368 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

const ll MAXN = 1E6+16;
ii wh[MAXN];
vll mat[MAXN];
ll n;
ll h, w;

#define mid ((l+r)>>1)
#define off (2*(mid-l+1))
struct SegTree {
    struct Node {
        ll minN;
        ll couN;
        ll lazy;

        Node operator+ (const Node &o) const {
            return {
                min(minN, o.minN),
                (minN <= o.minN ? couN : 0) + (o.minN <= minN ? o.couN : 0),
                0
            };
        }
    };
    vector <Node> tree;
    ll n;
    
    void init (ll n) {
        tree.assign(2*n, Node{ 0, 1, 0 });
        SegTree::n = n;
        dfs_init(0, n-1, 0);
    }

    void dfs_init (ll l, ll r, ll id) {
        if (l == r) return;
        dfs_init(l, mid, id+1);
        dfs_init(mid+1, r, id+off);
        tree[id] = tree[id+1] + tree[id+off];
    }

    void push (ll l, ll r, ll id) {
        if (!tree[id].lazy) return;
        tree[id].minN += tree[id].lazy;
        if (l < r) {
            tree[id+1].lazy += tree[id].lazy;
            tree[id+off].lazy += tree[id].lazy;
        }
        tree[id].lazy = 0;
    }

    void update (ll ql, ll qr, ll val) { update(ql, qr, val, 0, n-1, 0); }
    void update (ll ql, ll qr, ll val, ll l, ll r, ll id) {
        push(l, r, id);
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) {
            tree[id].lazy = val;
            push(l, r, id);
            return;
        }
        update(ql, qr, val, l, mid, id+1);
        update(ql, qr, val, mid+1, r, id+off);
        tree[id] = tree[id+1] + tree[id+off];
    }

    Node query () {
        push(0, n-1, 0);
        return tree[0];
    }
} st;

vii intervs (ll i, ll j) {
    assert(0 <= i && i <= h);
    assert(0 <= j && j <= w);
    vii nums;
    if (i > 0 && j > 0)
        nums.push_back({ mat[i-1][j-1], 0 });
    else
        nums.push_back({ n, 0 });
    if (i > 0 && j < w)
        nums.push_back({ mat[i-1][j], 1 });
    else
        nums.push_back({ n, 1 });
    if (i < h && j > 0)
        nums.push_back({ mat[i][j-1], 2 });
    else
        nums.push_back({ n, 2 });
    if (i < h && j < w)
        nums.push_back({ mat[i][j], 3 });
    else
        nums.push_back({ n, 3 });
    sort(nums.begin(), nums.end());
    vii ans;
    if ((nums[0].second ^ nums[1].second) == 3) { // opposite corners in first, second turned on
        ans.push_back({ nums[0].first, nums[3].first-1 });
    } else {
        ans.push_back({ nums[0].first, nums[1].first-1 });
        ans.push_back({ nums[2].first, nums[3].first-1 });
    }
    return ans;
}

void give_initial_chart (int h, int w, vi r, vi c) {
    ::h = h, ::w = w;
    n = h*w;
    st.init(n);
    for (ll i = 0; i < n; i++) {
        wh[i] = ii{ r[i], c[i] };
    }
    for (ll i = 0; i < n; i++) {
        mat[r[i]].push_back(i);
    }
    for (ll i = 0; i < h; i++) {
        sort(mat[i].begin(), mat[i].end(), [&](ll a, ll b) {
            return c[a] < c[b];
        });
    }
    for (ll i = 0; i <= h; i++) {
        for (ll j = 0; j <= w; j++) {
            for (auto [l, r] : intervs(i, j)) {
                st.update(l, r, +1);
            }
        }
    }
}

int swap_seats (int a, int b) {
    auto [ai, aj] = wh[a];
    auto [bi, bj] = wh[b];
    vii mySet;
    mySet.push_back({ ai, aj });
    mySet.push_back({ ai, aj+1 });
    mySet.push_back({ ai+1, aj });
    mySet.push_back({ ai+1, aj+1 });
    mySet.push_back({ bi, bj });
    mySet.push_back({ bi, bj+1 });
    mySet.push_back({ bi+1, bj });
    mySet.push_back({ bi+1, bj+1 });
    sort(mySet.begin(), mySet.end());
    mySet.resize(unique(mySet.begin(), mySet.end()) - mySet.begin());
    for (auto [i, j] : mySet)
        for (auto [l, r] : intervs(i, j))
            st.update(l, r, -1);
    swap(wh[a], wh[b]);
    swap(mat[ai][aj], mat[bi][bj]);
    for (auto [i, j] : mySet)
        for (auto [l, r] : intervs(i, j))
            st.update(l, r, +1);
    return st.query().couN;
}

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