Submission #1018396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018396		RaresFelix	Seats (IOI18_seats)	C++17	20 / 100	429 ms	200532 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;
const int INF = 1e9;


int n, m;
vector<vi> T;
vi R, C;

using i4 = array<int, 4>;

const int MN = 1e6;
namespace AINT {
    int n;
    i4 Mi[4 * MN], Lz[4 * MN];
    vi Nr;
    void build(int u, int s, int d, const vi S[4]);
    void init(int N, const vi S[4]) {
        n = N;
        Nr.assign(4 * N, 0);
        for(int i = 0; i < 4 * N; ++i)
            Mi[i] = Lz[i] = i4{0, 0, 0, 0};
        build(1, 0, n - 1, S);
    }

    void build(int u, int s, int d, const vi S[4]) {
        if(s != d) {
            build(u << 1, s, (s + d) >> 1, S);
            build(u << 1 | 1, ((s + d) >> 1) + 1, d, S);
            Mi[u] = min(Mi[u << 1], Mi[u << 1 | 1]);
            Nr[u] = 0;
            if(Mi[u] == Mi[u << 1]) Nr[u] += Nr[u << 1];
            if(Mi[u] == Mi[u << 1 | 1]) Nr[u] += Nr[u << 1 | 1];
        } else {
            for(int a = 0; a < 4; ++a) Mi[u][a] = S[a][s];
            Nr[u] = 1;
        }
    }

    void prop(int u, int s, int d) {
        for(int a = 0; a < 4; ++a) {
            Mi[u][a] += Lz[u][a];
            if(s != d) {
                Lz[u << 1][a] += Lz[u][a];
                Lz[u << 1 | 1][a] += Lz[u][a];
            }
            Lz[u][a] = 0;
        }
    }
    void update(int l, int r, i4 v, int u, int s, int d) {
        prop(u, s, d);
        if(d < l || r < s) return;
        if(l <= s && d <= r) {
            for(int a = 0; a < 4; ++a) Lz[u][a] += v[a];
            prop(u, s, d);
            return;
        }
        update(l, r, v, u << 1, s, (s + d) >> 1);
        update(l, r, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
        Mi[u] = min(Mi[u << 1], Mi[u << 1 | 1]);
        Nr[u] = 0;
        if(Mi[u] == Mi[u << 1]) Nr[u] += Nr[u << 1];
        if(Mi[u] == Mi[u << 1 | 1]) Nr[u] += Nr[u << 1 | 1];
    }
    void update(int l, int r, i4 v) {
        if(l > r) return;
        update(l, r, v, 1, 0, n - 1);
    }
    int cnt() {
        if(Mi[1] == i4{1, 1, 1, 1}) return Nr[1];
        return 0;
    }
};

using ii4 = array<ii, 4>;

static pair<ii4, ii4> recalc_int(int i, int j) {
    ///va recalcula intervalele de relevanta, Lin si Pat
    ///0 <- (i, j)
    ///1
    ii4 lin, pat;
    lin[0] = {T[i + 1][j], T[i][j] - 1};
    pat[0] = {max(T[i + 1][j], T[i + 1][j + 1]), min(T[i][j], T[i][j + 1]) - 1};
    /// 1 -> dreapta (1*, 0)
    lin[1] = {T[i][j], T[i][j + 1] - 1};
    pat[1] = {max(T[i][j], T[i + 1][j]), min(T[i][j + 1], T[i + 1][j + 1]) - 1};

    /// 2 -> jos
    /// 1*
    /// 0
    lin[2] = {T[i][j], T[i + 1][j] - 1};
    pat[2] = {max(T[i][j], T[i][j + 1]), min(T[i + 1][j], T[i + 1][j + 1]) - 1};

    ///3 -> stanga
    /// 0* 1
    lin[3] = {T[i][j + 1], T[i][j] - 1};
    pat[3] = {max(T[i][j + 1], T[i + 1][j + 1]), min(T[i][j], T[i + 1][j]) - 1};

    return {lin, pat};
}

int h, w;

void give_initial_chart(int H, int W, vi R0, vi C0) {
    R = R0; C = C0;
    n = H + 2; m = W + 2;
    h = H; w = W;
    T.resize(n, vi(m, INF));
    for(int i = 0; i < R.size(); ++i) {
        T[R[i] + 1][C[i] + 1] = i;
    }
    vi S[4];
    for(int a = 0; a < 4; ++a) S[a].resize(h * w, 0);
    for(int i = 0; i <= H; ++i)
        for(int j = 0; j <= W; ++j) {
            auto [LV, PV] = recalc_int(i, j);
            for(int d = 0; d < 4; ++d) {

                auto [l1, r1] = LV[d];
                //add(l1, r1, d, 1);
                if(l1 <= r1) {
                    S[d][l1]++;
                    if(r1 + 1 < h * w) -- S[d][r1 + 1];
                }

                auto [l2, r2] = PV[d];
                if(l2 <= r2) {
                    //add(l2, r2, d, -1);
                    S[d][l2]--;
                    if(r2 + 1 < h * w) ++S[d][r2 + 1];
                }
            }
        }
    for(int i = 1; i < h * w; ++i) {
        for(int d = 0; d < 4; ++d)
            S[d][i] += S[d][i - 1];
    }
    AINT::init(h * w, S);
}

void change(int a, int b) {
    swap(T[R[a] + 1][C[a] + 1], T[R[b] + 1][C[b] + 1]);
    swap(R[a], R[b]);
    swap(C[a], C[b]);
}

static void reset(int l, int c, int a, int b) {
    ///un 3 x 3 in apropiere
    auto add = [&](int l, int r, int d, int sgn) {
        i4 v{0, 0, 0, 0}; v[d] = sgn;
        AINT::update(l, r, v);
    };
    for(int i = max(0, l - 1); i <= min(n - 2, l + 1); ++i) {
        for(int j = max(0, c - 1); j <= min(m - 2, c + 1); ++j) {
                auto [LV, PV] = recalc_int(i, j);
                change(a, b);
                auto [NLV, NPV] = recalc_int(i, j);

                for(int d = 0; d < 4; ++d) {
                    if(NLV[d] != LV[d]) {
                        auto [l1, r1] = LV[d];
                        auto [ll1, rr1] = NLV[d];
                        add(l1, r1, d, -1);
                        add(ll1, rr1, d, 1);
                    }

                    if(NPV[d] != PV[d]) {
                        auto [l2, r2] = PV[d];
                        add(l2, r2, d, 1);
                        auto [ll2, rr2] = NPV[d];
                        add(ll2, rr2, d, -1);
                    }
                }
                change(a, b);
        }
    }
}

int swap_seats(int a, int b) {
    reset(R[a], C[a], a, b);
    reset(R[b], C[b], a, b);
    change(a, b);
    return AINT::cnt();
}

Compilation message (stderr)

seats.cpp: In function 'void give_initial_chart(int, int, vi, vi)':
seats.cpp:115:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for(int i = 0; i < R.size(); ++i) {
      |                    ~~^~~~~~~~~~

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