Submission #1199177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199177		fv3	Seats (IOI18_seats)	C++20	100 / 100	1996 ms	103464 KiB

seats

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

#ifdef LOCAL
#include "/home/fv3/prog/debug/debug.h"
#else
#define debug(...) 42
#endif

vector<vector<int>> a;
vector<int> R, C;
int W, H, N;

bool evenSquare(int i, int x, int y) {
    int sum = (int(a[R[i]+y][C[i]+x] < i) + int(a[R[i]+1+y][C[i]+x] < i) +
               int(a[R[i]+1+y][C[i]+1+x] < i) + int(a[R[i]+y][C[i]+1+x] < i)) % 2;
    return sum % 2 == 0;
}

struct segtree {
    int nt = 1;
    vector<int> mn, cnt, add;

    void init() {
        while (nt < N) {
            nt <<= 1;
        }

        mn = vector<int>(2*nt, 1 << 30);
        cnt = vector<int>(2*nt, 1);
        add = vector<int>(2*nt);

        debug(a);
        debug(R);
        debug(C);

        mn[nt] = 4;
        for (int i = 1; i < N; i++) {
            mn[nt+i] = mn[nt+i-1];

            if (evenSquare(i, 0, 0)) {
                mn[nt+i]++;
            } else {
                mn[nt+i]--;
            }

            if (evenSquare(i, 0, -1)) {
                mn[nt+i]++;
            } else {
                mn[nt+i]--;
            }

            if (evenSquare(i, -1, 0)) {
                mn[nt+i]++;
            } else {
                mn[nt+i]--;
            }

            if (evenSquare(i, -1, -1)) {
                mn[nt+i]++;
            } else {
                mn[nt+i]--;
            }
        }

        for (int i = nt-1; i >= 1; i--) {
            merge(i, i*2, i*2|1);
        }
    }

    void prop(int k) {
        mn[k] += add[k];
        if (k < nt) {
            add[k*2] += add[k];
            add[k*2|1] += add[k];
        }
        add[k] = 0;
    }

    void update(int l, int r, int k, int tl, int tr, int val) {
        prop(k);
        if (tl > r || tr < l) return;
        if (tl >= l && tr <= r) {
            add[k] += val;
            prop(k);
            return;
        }
        int c = (tl + tr) / 2;
        update(l, r, k*2, tl, c, val);
        update(l, r, k*2|1, c+1, tr, val);

        merge(k, k*2, k*2|1);
    }

    void merge(int i, int c1, int c2) {
        if (mn[c1] == mn[c2]) {
            cnt[i] = cnt[c1] + cnt[c2];
        } else if (mn[c1] < mn[c2]) {
            cnt[i] = cnt[c1];
        } else {
            cnt[i] = cnt[c2];
        }
        mn[i] = min(mn[c1], mn[c2]);
    }
};

segtree st;
void give_initial_chart(int H_, int W_, vector<int> R_, vector<int> C_)  {
    W = W_; H = H_;
    N = W * H;

    R = R_; C = C_;
    for (int i = 0; i < N; i++) {
        R[i]++; C[i]++;
    }
    a = vector<vector<int>>(H+2, vector<int>(W+2, N));
    for (int i = 0; i < N; i++) {
        a[R[i]][C[i]] = i;
    }
    
    st.init();
    debug(st.mn);
    debug(st.cnt);
}

void updateSquare(int i, int x, int y, bool rem) {
    vector<int> v = {a[R[i]+y][C[i]+x], a[R[i]+y+1][C[i]+x], a[R[i]+y][C[i]+x+1], a[R[i]+y+1][C[i]+x+1]};
    sort(v.begin(), v.end());

    st.update(v[0], v[1]-1, 1, 0, st.nt-1, rem ? -1 : 1);
    st.update(v[2], v[3]-1, 1, 0, st.nt-1, rem ? -1 : 1);
}

int swap_seats(int u, int v)  {
    updateSquare(u,  0,  0, true);
    updateSquare(u, -1,  0, true);
    updateSquare(u,  0, -1, true);
    updateSquare(u, -1, -1, true);

    updateSquare(v,  0,  0, true);
    updateSquare(v, -1,  0, true);
    updateSquare(v,  0, -1, true);
    updateSquare(v, -1, -1, true);

    swap(a[R[u]][C[u]], a[R[v]][C[v]]);
    swap(R[u], R[v]); swap(C[u], C[v]);

    updateSquare(u,  0,  0, false);
    updateSquare(u, -1,  0, false);
    updateSquare(u,  0, -1, false);
    updateSquare(u, -1, -1, false);

    updateSquare(v,  0,  0, false);
    updateSquare(v, -1,  0, false);
    updateSquare(v,  0, -1, false);
    updateSquare(v, -1, -1, false);
    return st.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