Submission #1226725

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226725		Hamed_Ghaffari	Seats (IOI18_seats)	C++20	100 / 100	2704 ms	119696 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

#define X first
#define Y second
#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)

const int MXN = 1e6+2;

namespace H1 {
    int h, w;
    vector<int> R, C;
    vector<vector<int>> A;
    pair<pii, int> seg[MXN<<2];
    pii lz[MXN<<2];

    inline pair<pii, int> merge(pair<pii, int> x, pair<pii, int> y) {
        return x.X == y.X ? make_pair(x.X, x.Y+y.Y) : min(x, y);
    }

    void build(int l=0, int r=h*w, int id=1) {
        lz[id] = {0, 0};
        if(r-l == 1) {
            seg[id] = {{0, 0}, 1};
            return;
        }
        build(l, mid, lc);
        build(mid, r, rc);
    }

    inline void apply(pii x, int id) {
        seg[id].X.X += x.X; seg[id].X.Y += x.Y;
        lz[id].X += x.X; lz[id].Y += x.Y;
    }

    inline void push(int id) {
        if(lz[id].X || lz[id].Y) {
            apply(lz[id], lc);
            apply(lz[id], rc);
            lz[id] = {0, 0};
        }
    }

    void upd(int s, int e, pii x, int l=0, int r=h*w, int id=1) {
        if(s>=r || l>=e) return;
        if(s<=l && r<=e) {
            apply(x, id);
            return;
        }
        push(id);
        upd(s, e, x, l, mid, lc);
        upd(s, e, x, mid, r, rc);
        seg[id] = merge(seg[lc], seg[rc]);
    }

    inline void add(int i, int j, int z) {
        if(j==-1) upd(A[i][0], h*w, {z, 0});
        else if(j+1==w) upd(A[i][w-1], h*w, {z, 0});
        else upd(min(A[i][j], A[i][j+1]), max(A[i][j], A[i][j+1]), {z, 0});
    }

    void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
        A = vector<vector<int>>(h=H, vector<int>(w=W));
        assert(H==1);
        H1::R = R;
        H1::C = C;
        for(int i=0; i<h*w; i++)
            A[R[i]][C[i]] = i;
        build();
        for(int j=-1; j<w; j++)
            add(0, j, 1);
    }
    int swap_seats(int a, int b) {
        add(R[a], C[a]-1, -1);
        add(R[a], C[a], -1);
        add(R[b], C[b]-1, -1);
        add(R[b], C[b], -1);

        swap(A[R[a]][C[a]], A[R[b]][C[b]]);
        add(R[a], C[a]-1, 1);
        add(R[a], C[a], 1);
        add(R[b], C[b]-1, 1);
        add(R[b], C[b], 1);
        swap(R[a], R[b]);
        swap(C[a], C[b]);

        return seg[1].X == make_pair(2, 0) ? seg[1].Y : 0;
    }
}

int h, w;
vector<int> R, C;
vector<vector<int>> A;
pair<pii, int> seg[MXN<<2];
pii lz[MXN<<2];

inline pair<pii, int> merge(pair<pii, int> x, pair<pii, int> y) {
    return x.X == y.X ? make_pair(x.X, x.Y+y.Y) : min(x, y);
}

void build(int l=0, int r=h*w, int id=1) {
    lz[id] = {0, 0};
    if(r-l == 1) {
        seg[id] = {{0, 0}, 1};
        return;
    }
    build(l, mid, lc);
    build(mid, r, rc);
}

inline void apply(pii x, int id) {
    seg[id].X.X += x.X; seg[id].X.Y += x.Y;
    lz[id].X += x.X; lz[id].Y += x.Y;
}

inline void push(int id) {
    if(lz[id].X || lz[id].Y) {
        apply(lz[id], lc);
        apply(lz[id], rc);
        lz[id] = {0, 0};
    }
}

void upd(int s, int e, pii x, int l=0, int r=h*w, int id=1) {
    if(s>=r || l>=e) return;
    if(s<=l && r<=e) {
        apply(x, id);
        return;
    }
    push(id);
    upd(s, e, x, l, mid, lc);
    upd(s, e, x, mid, r, rc);
    seg[id] = merge(seg[lc], seg[rc]);
}

inline void add(int i, int j, int z) {
    int mn1=h*w, mn2=h*w, mx1=0, mx2=0;
    for(int k=max(0, i); k<=i+1 && k<h; k++)
        for(int l=max(0, j), x; l<=j+1 && l<w; l++) {
            x = 0<=k && k<h && 0<=l && l<w ? A[k][l] : h*w;
            mn2 = min(mn2, x);
            if(mn2<mn1) swap(mn1, mn2);
            mx2 = max(mx2, x);
            if(mx2>mx1) swap(mx1, mx2);
        }
    upd(mn1, mn2, {0, z});
    if(0<=i && i+1<h && 0<=j && j+1<w) upd(mx2, mx1, {z, 0});
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    A = vector<vector<int>>(h=H, vector<int>(w=W));
    if(h==1) {
        H1::give_initial_chart(H, W, R, C);
        return;
    }
    ::R = R;
    ::C = C;
    for(int i=0; i<h*w; i++)
        A[R[i]][C[i]] = i;
    build();
    for(int i=-1; i<h; i++)
        for(int j=-1; j<w; j++)
            add(i, j, 1);
}
int swap_seats(int a, int b) {
    if(h==1) return H1::swap_seats(a, b);
    add(R[a]-1, C[a]-1, -1);
    add(R[a]-1, C[a], -1);
    add(R[a], C[a]-1, -1);
    add(R[a], C[a], -1);
    add(R[b]-1, C[b]-1, -1);
    add(R[b]-1, C[b], -1);
    add(R[b], C[b]-1, -1);
    add(R[b], C[b], -1);

    swap(A[R[a]][C[a]], A[R[b]][C[b]]);
    add(R[a]-1, C[a]-1, 1);
    add(R[a]-1, C[a], 1);
    add(R[a], C[a]-1, 1);
    add(R[a], C[a], 1);
    add(R[b]-1, C[b]-1, 1);
    add(R[b]-1, C[b], 1);
    add(R[b], C[b]-1, 1);
    add(R[b], C[b], 1);
    swap(R[a], R[b]);
    swap(C[a], C[b]);

    return seg[1].X == make_pair(0, 4) ? seg[1].Y : 0;
}

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