Submission #904957

#	Time	Username	Problem	Language	Result	Execution time	Memory
904957		Trisanu_Das	Seats (IOI18_seats)	C++17	37 / 100	4043 ms	180840 KiB

seats

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

using namespace std;

const int MAX_N = 1000005;
vector<int> r;
pair<int, int> V[MAX_N];
pair<int, int> mx[MAX_N], mi[MAX_N];
vector<int> lst;

struct inout_pq {
    priority_queue<int> in, out;

    void add(int x) { in.push(-x); }

    void delect(int x) { out.push(-x); }

    int return_top() {
        while (in.size() && out.size() && in.top() == out.top()) {
            in.pop();
            out.pop();
        }
        if (in.size()) return -in.top();
        return 0;
    }
} X[MAX_N], Y[MAX_N];

int h, w, ans;

int sp(int a, int b) {
    pair<int, int> x, y;
    swap(V[a], V[b]);
    if (a > b) swap(a, b);
    a = a ? a : a + 1;
    mx[0] = mi[0] = V[0];
    for (int i = a; i <= b; i++) {
        ans -= ((mx[i].first - mi[i].first + 1) * (mx[i].second - mi[i].second + 1) == (i + 1)) ? 1 : 0;
        mx[i].first = max(mx[i - 1].first, V[i].first);
        mx[i].second = max(mx[i - 1].second, V[i].second);
        mi[i].first = min(mi[i - 1].first, V[i].first);
        mi[i].second = min(mi[i - 1].second, V[i].second);
        ans += ((mx[i].first - mi[i].first + 1) * (mx[i].second - mi[i].second + 1) == (i + 1)) ? 1 : 0;
    }
    return ans;
}

void sp_init() {
    mx[0] = mi[0] = V[0];
    swap(V[0], V[h * w - 1]);
    ans = 1;
    ans = sp(0, h * w - 1);
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    int i;
    h = H;
    w = W;
    for (i = 0; i < H * W; i++) V[i] = {R[i], C[i]};
    if (h + w >= 10000) {
        sp_init();
        return;
    }
    for (i = 0; i < H * W; i++) {
        X[R[i]].add(i);
        Y[C[i]].add(i);
    }
}

int swap_seats(int a, int b) {
    int i;
    if (h + w >= 10000) return sp(a, b);
    X[V[a].first].delect(a);
    Y[V[a].second].delect(a);
    X[V[b].first].delect(b);
    Y[V[b].second].delect(b);
    swap(V[a], V[b]);
    X[V[a].first].add(a);
    Y[V[a].second].add(a);
    X[V[b].first].add(b);
    Y[V[b].second].add(b);
    lst.clear();
    lst.resize(0);
    for (i = 0; i < h; i++) lst.push_back(X[i].return_top());
    for (i = 0; i < w; i++) lst.push_back(Y[i].return_top());
    sort(lst.begin(), lst.end());
    lst.erase(unique(lst.begin(), lst.end()), lst.end());
    pair<int, int> x, y;
    ans = 1;
    x = {V[0].first, V[0].first};
    y = {V[0].second, V[0].second};
    for (int p : lst) {
        ans += ((x.second - x.first + 1) * (y.second - y.first + 1) == p);
        y.first = min(y.first, V[p].second);
        y.second = max(y.second, V[p].second);
        x.first = min(x.first, V[p].first);
        x.second = max(x.second, V[p].first);
    }
    return ans;
}

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