Submission #1077342

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077342		vjudge1	Seats (IOI18_seats)	C++17	70 / 100	4061 ms	172992 KiB

seats

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

using namespace std;

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

int h, w;
vi R, C;

vector<vi> A;

namespace AINT {
    int n;
    vector<ii> V, Lz;
    vi Nr;
    void build(int u, int s, int d);
    void init(int N) {
        n = N;
        V.resize(4 * n, ii{0, 0});
        Lz.resize(4 * n, ii{0, 0});
        Nr.resize(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) {
        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};
    }

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

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

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

};

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

bool conex(vi &V, int lim) {
    int tip = 0;
    for(auto it : V) {
        if(it <= lim) {
            if(tip == 2) return false;
            if(tip == 0) tip = 1;
        } else if(tip == 1) {
            tip = 2;
        }
    }
    return true;
}



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