Submission #1018377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018377		RaresFelix	Seats (IOI18_seats)	C++17	11 / 100	4072 ms	262144 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>

using namespace std;

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

int n, m;
vector<vi> T;
vector<vector<ii> > Lin[4];
vector<vector<ii> > Pat[4];
vi R, C;

using i4 = array<int, 4>;

struct AINT {
    int n;
    vector<i4> Mi, Lz, V;
    vi Nr;
    AINT() {}
    AINT(int N) : n(N), Mi(4 * N, {0, 0, 0, 0}), Lz(4 * N, {0, 0, 0, 0}), V(N, {0, 0, 0, 0}), Nr(4 * N, 0) {
        build(1, 0, n - 1);
    }

    void build(int u, int s, int d) {
        Nr[u] = d - s + 1;
        if(s != d) {
            build(u << 1, s, (s + d) >> 1);
            build(u << 1 | 1, ((s + d) >> 1) + 1, d);
        }
    }

    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) {
//        for(int i = l; i <= min(r, n - 1); ++i) {
//            for(int a = 0; a < 4; ++a)
//                V[i][a] += v[a];
//        }
//        return;

        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;
    }
};

void recalc_int(int i, int j) {
    ///va recalcula intervalele de relevanta, Lin si Pat
    ///0 <- (i, j)
    ///1
    Lin[0][i][j] = {T[i + 1][j], T[i][j] - 1};
    Pat[0][i][j] = {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][i][j] = {T[i][j], T[i][j + 1] - 1};
    Pat[1][i][j] = {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][i][j] = {T[i][j], T[i + 1][j] - 1};
    Pat[2][i][j] = {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][i][j] = {T[i][j + 1], T[i][j] - 1};
    Pat[3][i][j] = {max(T[i][j + 1], T[i + 1][j + 1]), min(T[i][j], T[i + 1][j]) - 1};
}

AINT Sol;

void give_initial_chart(int H, int W, vi R0, vi C0) {
    R = R0; C = C0;
    n = H + 2; m = W + 2;
    T.resize(n, vi(m, INF));
    Sol = AINT(W * H);
    for(int d = 0; d < 4; ++d) {
        Lin[d].resize(H + 1, vector<ii>(W + 1, ii{-1, 0}));
        Pat[d].resize(H + 1, vector<ii>(W + 1, ii{-1, 0}));
    }
    for(int i = 0; i < R.size(); ++i) {
        T[R[i] + 1][C[i] + 1] = i;
    }
    auto add = [&](int l, int r, int d, int sgn) {
        i4 v{0, 0, 0, 0}; v[d] = sgn;
        Sol.update(l, r, v);
    };
    for(int i = 0; i <= H; ++i)
        for(int j = 0; j <= W; ++j) {
            recalc_int(i, j);
            for(int d = 0; d < 4; ++d) {

                auto [l1, r1] = Lin[d][i][j];
                add(l1, r1, d, 1);

                auto [l2, r2] = Pat[d][i][j];
                add(l2, r2, d, -1);
            }
        }
}

void reset(int l, int c) {
    ///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;
        Sol.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) {
                for(int d = 0; d < 4; ++d) {
                    auto [l1, r1] = Lin[d][i][j];
                    add(l1, r1, d, -1);

                    auto [l2, r2] = Pat[d][i][j];
                    add(l2, r2, d, 1);
                }

                recalc_int(i, j);

                for(int d = 0; d < 4; ++d) {
                    auto [ll1, rr1] = Lin[d][i][j];
                    add(ll1, rr1, d, 1);

                    auto [ll2, rr2] = Pat[d][i][j];
                    add(ll2, rr2, d, -1);
                }
        }
    }
}

int swap_seats(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]);
    reset(R[a], C[a]);
    reset(R[b], C[b]);
    return Sol.cnt();
}

Compilation message (stderr)

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

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