Submission #1077350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077350		vjudge1	Seats (IOI18_seats)	C++17	70 / 100	4056 ms	119812 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,fma")

using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;

int h, w;
vi R, C;

vector<vi> A;

const int MN = 1000000;

namespace AINT {
    int n;
    ii V[4 * MN], Lz[4 * MN];
    int Nr[4 * MN];
    static void build(int u, int s, int d);
    static void init(int N) {
        n = N;
        build(1, 0, n - 1);
    }

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

    static void prop(int u, int s, int d) {
        if(!Lz[u].first && !Lz[u].second) return;
        V[u].first += Lz[u].first;
        V[u].second += Lz[u].second;
        if(s != d) {
            Lz[u << 1].first += Lz[u].first;
            Lz[u << 1 | 1].first += Lz[u].first;
            Lz[u << 1].second += Lz[u].second;
            Lz[u << 1 | 1].second += Lz[u].second;
        }
        Lz[u] = ii{0, 0};
    }

    static void update(int l, int r, ii v, int u, int s, int d) {
        prop(u, s, d);
        if(d < l || r < s) return;
        if(l <= s && d <= r) {
            Lz[u].first += v.first;
            Lz[u].second += v.second;
            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);
        V[u] = min(V[u << 1], V[u << 1 | 1]);
        Nr[u] = Nr[u << 1] * (V[u] == V[u << 1]) 
            + Nr[u << 1 | 1] * (V[u] == V[u << 1 | 1]);
    }

    static void update(int l, int r, ii v) {
        update(l, r, v, 1, 0, n - 1);
    }

    static int query() {
        if(V[1] != ii{0, 4}) return 0;
        return Nr[1];
    }

};

static void update(int l, int c, int sgn) {
    if(l < 0 || c < 0 || l > h + 1 || c > w + 1) return;
    vi V = {A[l][c], A[l][c + 1], A[l + 1][c], A[l + 1][c + 1]};
    sort(V.begin(), V.end());
    AINT::update(V[0], V[1] - 1, {0, sgn});
    AINT::update(V[2], V[3] - 1, {sgn, 0});
}

const int INF = 1e9;

void give_initial_chart(int H, int W, vi R0, vi C0) {
    h = H; w = W;
    AINT::init(h * w);
    R = R0; C = C0;
    A.assign(h + 2, vi(w + 2, INF));
    for(int i = 0; i < h * w; ++i) A[R[i] + 1][C[i] + 1] = i;
    for(int l = 0; l <= h; ++l)
        for(int c = 0; c <= w; ++c)
            update(l, c, 1);
}

int swap_seats(int a, int b) {
    set<ii> Poz;
    for(int x = R[a] - 1; x <= R[a] + 1; ++x)
        for(int y = C[a] - 1; y <= C[a] + 1; ++y)
            Poz.insert({x, y});
    for(int x = R[b] - 1; x <= R[b] + 1; ++x)
        for(int y = C[b] - 1; y <= C[b] + 1; ++y)
            Poz.insert({x, y});
    for(auto [x, y] : Poz) update(x, y, -1);
    swap(R[a], R[b]); swap(C[a], C[b]);
    swap(A[R[a] + 1][C[a] + 1], A[R[b] + 1][C[b] + 1]);
    for(auto [x, y] : Poz) update(x, y, 1);
    int re = AINT::query();
    return re;
}

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