Submission #1077357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077357		vjudge1	Seats (IOI18_seats)	C++17	100 / 100	2785 ms	120004 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;
int S0[MN], S1[MN];

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

    static void build(int u, int s, int d) {
        if(s != d) {
            build(u << 1, s, (s + d) >> 1);
            build(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]);
        } else {
            V[u] = {S0[s], S1[s]};
            Nr[u] = 1;
            return;
        }
    }

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


static void update0(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());
    auto add = [&](int l, int r, int v1, int v2) {
        l = max(l, 0);
        if(l > AINT::n || r < 0) return;
        r = min(r, AINT::n - 1);
        if(v1) {
            S0[l] += v1;
            if(r + 1 < AINT::n) S0[r + 1] -= v1;
        }
        if(v2) {
            S1[l] += v2;
            if(r + 1 < AINT::n) S1[r + 1] -= v2;
        }
    };
    add(V[0], V[1] - 1, 0, sgn);
    add(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)
            update0(l, c, 1);
    for(int i = 1; i < h * w; ++i) {
        S0[i] += S0[i - 1];
        S1[i] += S1[i - 1];
    }
    AINT::build(1, 0, AINT::n - 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: 30 / 30