Submission #78799

#	Time	Username	Problem	Language	Result	Execution time	Memory
78799		wleung_bvg	Seats (IOI18_seats)	C++14	100 / 100	3217 ms	63964 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define all(a) (a).begin(),(a).end()
#define For(i,a,b) for(auto i=(a);i<(b);i++)
#define FOR(i,b) For(i,0,b)
#define Rev(i,a,b) for(auto i=(a);i>(b);i--)
#define REV(i,a) Rev(i,a,-1)
#define FORE(i,a) for(auto&&i:a)
#define sz(a) (int((a).size()))
#define MIN(a,b) ((a)=min((a),(b)))
#define MAX(a,b) ((a)=max((a),(b)))
using ll=long long;using ld=long double;using uint=unsigned int;using ull=unsigned long long;
using pii=pair<int,int>;using pll=pair<ll,ll>;using pill=pair<int,ll>;using plli=pair<ll,int>;using pdd=pair<double,double>;using pld=pair<ld,ld>;
constexpr const char nl='\n',sp=' ';constexpr const int INT_INF=0x3f3f3f3f;constexpr const ll LL_INF=0x3f3f3f3f3f3f3f3f;
constexpr const double D_INF=numeric_limits<double>::infinity();constexpr const ld LD_INF=numeric_limits<ld>::infinity();constexpr const double EPS=1e-9;

const int MAXHW = 1e6 + 5;

int H, W, N, M, VAL[MAXHW], L[MAXHW], R[MAXHW], C[MAXHW];
pii T[MAXHW * 2];

pii merge(const pii &l, const pii &r) {
    if (l.f < r.f) return l;
    else if (l.f > r.f) return r;
    else return mp(l.f, l.s + r.s);
}

void apply(int i, int v) {
    T[i].f += v;
    if (i < N) L[i] += v;
}

void pushup(int i) {
    while (i > 1) {
        i >>= 1;
        T[i] = merge(T[i << 1], T[i << 1 | 1]);
        T[i].f += L[i];
    }
}

void propagate(int i) {
    for (int h = M; h > 0; h--) {
        int ii = i >> h;
        if (L[ii] != 0) {
            apply(ii << 1, L[ii]);
            apply(ii << 1 | 1, L[ii]);
            L[ii] = 0;
        }
    }
}

void update(int l, int r, int v) {
    int l0 = l += N, r0 = r += N;
    propagate(l);
    propagate(r);
    for (; l <= r; l >>= 1, r >>= 1) {
        if (l & 1) apply(l++, v);
        if (!(r & 1)) apply(r--, v);
    }
    pushup(l0);
    pushup(r0);
}

int getVal(int r, int c) {
    return r < 0 || r >= H || c < 0 || c >= W ? N : VAL[r * W + c];
}

void updateSingle(int r, int c, int v) {
    vector<int> A;
    FOR(i, 2) FOR(j, 2) A.pb(getVal(r - i, c - j));
    sort(all(A));
    if (A[0] < A[1]) update(A[0], A[1] - 1, v);
    if (A[2] < A[3]) update(A[2], A[3] - 1, v);
}

void updateSquare(int r, int c, int v) {
    FOR(i, 2) FOR(j, 2) updateSingle(r + i, c + j, -1);
    VAL[r * W + c] = v;
    FOR(i, 2) FOR(j, 2) updateSingle(r + i, c + j, 1);
}

void give_initial_chart(int h, int w, vector<int> r, vector<int> c) {
    N = (H = h) * (W = w);
    M = 0;
    for (int i = 1; i <= N; M++) i <<= 1;
    FOR(i, N) {
        T[N + i] = mp(0, 1);
        L[i] = 0;
    }
    Rev(i, N - 1, 0) T[i] = merge(T[i << 1], T[i << 1 | 1]);
    FOR(i, N) VAL[(R[i] = r[i]) * W + (C[i] = c[i])] = i;
    FOR(i, H + 1) FOR(j, W + 1) updateSingle(i, j, 1);
    assert(T[1].f == 4);
}

int swap_seats(int a, int b) {
    updateSquare(R[a], C[a], b);
    updateSquare(R[b], C[b], a);
    swap(R[a], R[b]);
    swap(C[a], C[b]);
    assert(T[1].f == 4);
    return T[1].s;
}

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