Submission #1023896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023896		Dzadzo	Seats (IOI18_seats)	C++17	100 / 100	1576 ms	188632 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"
#define ll long long
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vp vector<pii>
#define vvp vector<vp>
#define vb vector<bool>
#define vvb vector<vb>
#define INF 2000000
#define MOD 1000000007
#define MAXN 1000000
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
class SegmentTree {
private:
    struct Node {
        int minVal;
        int count;
        int lazy;

        Node(int minVal = numeric_limits<int>::max(), int count = 0, int lazy = 0)
            : minVal(minVal), count(count), lazy(lazy) {}
    };

    vector<Node> tree;
    int size;

    void apply(int pos, int delta) {
        tree[pos].minVal += delta;
        tree[pos].lazy += delta;
    }

    void push(int pos) {
        apply(2 * pos, tree[pos].lazy);
        apply(2 * pos + 1, tree[pos].lazy);
        tree[pos].lazy = 0;
    }

    void pull(int pos) {
        if (tree[2 * pos].minVal < tree[2 * pos + 1].minVal) {
            tree[pos].minVal = tree[2 * pos].minVal;
            tree[pos].count = tree[2 * pos].count;
        } else if (tree[2 * pos].minVal > tree[2 * pos + 1].minVal) {
            tree[pos].minVal = tree[2 * pos + 1].minVal;
            tree[pos].count = tree[2 * pos + 1].count;
        } else {
            tree[pos].minVal = tree[2 * pos].minVal;
            tree[pos].count = tree[2 * pos].count + tree[2 * pos + 1].count;
        }
    }

public:
    SegmentTree(const vector<int>& arr) {
        size = arr.size();
        tree.resize(2 * size);
        for (int i = 1; i <= size; ++i) {
            tree[size + i - 1] = Node(arr[i - 1], 1);
        }
        for (int i = size - 1; i > 0; --i) {
            pull(i);
        }
    }

    void rangeAdd(int l, int r, int delta) {
        if( l > r ) return;

        l += size - 1;
        r += size - 1;
        int l0 = l, r0 = r;

        while (l <= r) {
            if (l % 2 == 1) apply(l++, delta);
            if (r % 2 == 0) apply(r--, delta);
            l /= 2;
            r /= 2;
        }

        for (int i : {l0 / 2, r0 / 2}) {
            while (i > 0) {
                push(i);
                pull(i);
                i /= 2;
            }
        }
    }

    pair<int, int> query() {
        push(1); // Ensure root is up-to-date
        return {tree[1].minVal, tree[1].count};
    }
};



SegmentTree st(vi(MAXN));
vvi arr;
vvb seen;
int n, H, W;

void add(int x, int y, int t) {
    vi v = {arr[x][y], arr[x + 1][y], arr[x][y + 1], arr[x + 1][y + 1]};
    sort(v.begin(), v.end());
    st.rangeAdd( v[0], min(n, v[1] - 1), t);
    st.rangeAdd( v[2], min(n, v[3] - 1), t);
}

vi R, C;

void give_initial_chart(int h, int w, vi r, vi c) {
    R = r;
    C = c;
    H = h;
    W = w;
    n = H * W;
    st.rangeAdd(n+1, MAXN, INF);
    arr.resize(H + 2, vi(W + 2, 0));
    seen.resize(H + 2, vb(W + 2, false));
    for (int i = 0; i < n; i++) arr[R[i] + 1][C[i] + 1] = i + 1;
    for (int i = 0; i <= W + 1; i++) arr[0][i] = arr[H + 1][i] = INF;
    for (int i = 0; i <= H + 1; i++) arr[i][0] = arr[i][W + 1] = INF;

    for (int i = 0; i <= H; i++)
        for (int j = 0; j <= W; j++)
            add(i, j, 1);
}

int swap_seats(int a, int b) {
    vp cur = {
        {R[a] + 1, C[a] + 1}, {R[a], C[a] + 1}, {R[a] + 1, C[a]},
        {R[a], C[a]}, {R[b] + 1, C[b] + 1}, {R[b] + 1, C[b]},
        {R[b], C[b] + 1}, {R[b], C[b]}
    };

    for (auto &[x, y] : cur) {
        if (!seen[x][y]) add(x, y, -1);
        seen[x][y] = true;
    }

    for (auto &[x, y] : cur) seen[x][y] = false;

    swap(arr[R[a] + 1][C[a] + 1], arr[R[b] + 1][C[b] + 1]);
    swap(R[a], R[b]);
    swap(C[a], C[b]);

    for (auto &[x, y] : cur) {
        if (!seen[x][y]) add(x, y, 1);
        seen[x][y] = true;
    }

    for (auto &[x, y] : cur) seen[x][y] = false;

    return st.query().S;
}
// signed main(){
//     give_initial_chart(1,5,{0, 0, 0, 0, 0},{0, 1, 2, 3, 4});
//     cout<<swap_seats(0,1)<<'\n';
//     cout<<swap_seats(0,3)<<'\n';
//     cout<<swap_seats(4,0)<<'\n';
// }

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