Submission #155571

#	Time	Username	Problem	Language	Result	Execution time	Memory
155571		rama_pang	Seats (IOI18_seats)	C++14	70 / 100	4051 ms	235368 KiB

seats

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

int N, H, W;
vector<int> R, C;
vector<vector<int>> seats;
vector<vector<int>> is_valid; //avoid double counting when updating

vector<int> updates_list;
vector<pair<int, int>> updates_pending;

inline void ADD(pair<int, int> &a, const pair<int, int> &b) {
    a.first += b.first;
    a.second += b.second;
}

/* a subset is rectangle if there are only 4 2*2 grid with 1 black squares and 0 2*2 grid woth 3 black squares */
struct segment_tree { /* number of 2*2 gird with 1 black square is always >= 4, so we can use segment tree and count minimum (4) */
    vector<pair<int, int>> tree, lazy;
    vector<int> cnt;
    
    inline void init(const int &n) {
        tree.assign(4 * n, {0, 0}); //minimums element
        lazy.assign(4 * n, {0, 0}); //lazy propagation
        cnt.assign(4 * n, 0); //number of minimum
        build(1, 0, n - 1);
    }
    
    inline void pull(const int &n) {
        tree[n] = min(tree[n * 2], tree[(n * 2) + 1]);
        cnt[n] = 0;
        if (tree[n] == tree[n * 2])     cnt[n] += cnt[n * 2];
        if (tree[n] == tree[(n * 2) + 1]) cnt[n] += cnt[(n * 2) + 1];
    }

    inline void push(const int &n) {
        ADD(tree[n * 2], lazy[n]);
        ADD(tree[n * 2 + 1], lazy[n]);
        ADD(lazy[n * 2], lazy[n]);
        ADD(lazy[n * 2 + 1], lazy[n]);
        lazy[n] = {0, 0};
    }

    void build(const int &n, const int &tl, const int &tr) {
        if (tl == tr) {
            cnt[n] = 1;
        } else {
            int mid = (tl + tr) / 2;
            build(n * 2, tl, mid);
            build(n * 2 + 1, mid + 1, tr);
            pull(n);
        }
    }
    
    void upd(const int &n, const int &tl, const int &tr, const int &le, const int &ri, const pair<int, int> &x) {
        if (ri < tl || tr < le || tl > tr) return;
        if (le <= tl && tr <= ri) {
            ADD(tree[n], x);
            ADD(lazy[n], x);
            return;
        }
        int mid = (tl + tr) / 2;
        push(n);
        upd(n * 2, tl, mid, le, ri, x);
        upd(n * 2 + 1, mid + 1, tr, le, ri, x);
        pull(n);
    }
    
    inline int query() {
        return (tree[1] == make_pair(4, 0))? cnt[1] : 0;
    }

} solver;

void update() {
    sort(updates_list.begin(), updates_list.end());
    updates_list.resize(unique(updates_list.begin(), updates_list.end()) - updates_list.begin());
    pair<int, int> cur_update = {0, 0};

    for (int i = 0; i < updates_list.size() - 1; i++) {
        ADD(cur_update, updates_pending[updates_list[i]]);
        solver.upd(1, 0, N - 1, updates_list[i], updates_list[i + 1] - 1, cur_update);
    }
    
    for (auto &i : updates_list) updates_pending[i] = {0, 0};
    updates_list.clear();
}

void push_update(const int &i, const int &j, const int &val) {
    if (is_valid[i][j] == 0 && val == -1) return;
    if (is_valid[i][j] == 1 && val == +1) return;
    is_valid[i][j] ^= 1;

    pair<int, int> grids[4];
    grids[0] = make_pair(seats[i][j], 0); //top left
    grids[1] = make_pair(seats[i][j + 1], 1); //top right
    grids[2] = make_pair(seats[i + 1][j + 1], 2); //bottom right
    grids[3] = make_pair(seats[i + 1][j], 3); //bottom left
    sort(grids, grids + 4);

    for (int k = 0; k < 3; k++) {
        int start = grids[k].first;
        int end = grids[k + 1].first;
        pair<int, int> updates = {0, 0};

        if (start >= end) {
            continue;
        } else if (k == 0) {
            updates = {val, 0};
        } else if (k == 1) {
            if ((grids[0].second ^ grids[1].second) == 2) { //diagonal black squares, mark that it's no longer a rectangle
                updates = {2 * val, 0}; //by assigning impossibility (minimum wil be >= 5, so no longer valid)
            } else {
                continue; //nothing changes
            }
        } else if (k == 2) {
            updates = {0, val}; //3 black squares
        }

        ADD(updates_pending[start], updates);
        ADD(updates_pending[end], {-updates.first, -updates.second});
        
        updates_list.emplace_back(start);
        updates_list.emplace_back(end);
    }   
}

void give_initial_chart(int h, int w, vector<int> r, vector<int> c) {
    H = h, W = w;
    N = H * W;
    R = r, C = c;

    seats.assign(H + 2, vector<int>(W + 2, N));
    is_valid.assign(H + 2, vector<int>(W + 2, 0));
    updates_pending.resize(N + 2, {0, 0});
    
    for (int i = 0; i < N; i++) seats[R[i] + 1][C[i] + 1] = i;
    for (int i = 0; i <= H; i++) {
        for (int j = 0; j <= W; j++) {
            push_update(i, j, +1);
        }
    }
    solver.init(N);
    update();
}   

int swap_seats(int a, int b) {
    for (int i = 0; i <= 1; i++) {
        for (int j = 0; j <= 1; j++) {
            push_update(R[a] + i, C[a] + j, -1);
            push_update(R[b] + i, C[b] + j, -1);
        }
    }
    
    swap(R[a], R[b]); swap(C[a], C[b]);
    swap(seats[R[a] + 1][C[a] + 1], seats[R[b] + 1][C[b] + 1]);

    for (int i = 0; i <= 1; i++) {
        for (int j = 0; j <= 1; j++) {
            push_update(R[a] + i, C[a] + j, +1);
            push_update(R[b] + i, C[b] + j, +1);
        }
    }

    update();
    return solver.query();
}

Compilation message (stderr)

seats.cpp: In function 'void update()':
seats.cpp:81:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < updates_list.size() - 1; i++) {
                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~

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