Submission #600908

#	Time	Username	Problem	Language	Result	Execution time	Memory
600908		piOOE	Seats (IOI18_seats)	C++17	37 / 100	4075 ms	188808 KiB

seats

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

using namespace std;

const int inf = 1e9 + 7;

template<typename T> bool ckmin(T& a, T b) {
    return !(a <= b) && (a = b), true;
}
template<typename T> bool ckmax(T& a, T b) {
    return !(a >= b) && (a = b), true;
}

struct SegTree {
    vector<int> mx, mn;
    int sz = 1;

    SegTree() = default;

    SegTree(int n, vector<int> a) {
        sz = n;
        mn.resize(sz << 1), mx.resize(sz << 1);
        for (int i = 0; i < n; ++i) {
            mn[i + sz] = mx[i + sz] = a[i];
        }
        for (int i = sz - 1; i > 0; --i) {
            mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
            mn[i] = min(mn[i << 1], mn[i << 1 | 1]);
        }
    }

    void modify(int i, int val) {
        i += sz;
        mn[i] = mx[i] = val;
        i >>= 1;
        while (i > 0) {
            mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
            mn[i] = min(mn[i << 1], mn[i << 1 | 1]);
            i >>= 1;
        }
    }

    pair<int, int> get(int l, int r) {
        l += sz;
        r += sz;
        int Max = -inf, Min = inf;
        while (l < r) {
            if (l & 1) {
                Max = max(Max, mx[l]);
                Min = min(Min, mn[l]);
                ++l;
            }
            if (r & 1) {
                --r;
                Max = max(Max, mx[r]);
                Min = min(Min, mn[r]);
            }
            l >>= 1;
            r >>= 1;
        }
        return {Min, Max};
    }

};

vector<int> x, y;
vector<bool> ans;

int n, m, s, sum = 0;

vector<set<int>> placeX, placeY;

SegTree R, C;

bool upd(int &mx, int &mn, int val) {
    bool yay = false;
    yay |= ckmax(mx, val);
    yay |= ckmin(mn, val);
    return yay;
}

void give_initial_chart(int H, int W, vector<int> _R, vector<int> _C) {
    swap(x, _R), swap(y, _C);
    n = H, m = W;
    s = n * m;
    R = SegTree(s, x);
    C = SegTree(s, y);
    ans.resize(s);
    placeX.assign(n, {});
    placeY.assign(m, {});
    int mxR = INT_MIN, mnR = INT_MAX;
    int mxC = mxR, mnC = mnR;
    for (int i = 0; i < s; ++i) {
        upd(mxR, mnR, x[i]);
        upd(mxC, mnC, y[i]);
        placeX[x[i]].insert(i);
        placeY[y[i]].insert(i);
        ans[i] = (mxR - mnR + 1) * (mxC - mnC + 1) == (i + 1);
        sum += ans[i];
    }
}

int swap_seats(int a, int b) {
    if (a > b) {
        swap(a, b);
    }
    if (n > 1000 || m > 1000) {
        swap(x[a], x[b]);
        swap(y[a], y[b]);
        R.modify(a, x[a]), R.modify(b, x[b]);
        C.modify(a, y[a]), C.modify(b, y[b]);
        auto [mnC, mxC] = C.get(0, a);
        auto [mnR, mxR] = R.get(0, a);
        for (int i = a; i <= b; ++i) {
            sum -= ans[i];
            upd(mxR, mnR, x[i]);
            upd(mxC, mnC, y[i]);
            ans[i] = (mxR - mnR + 1) * (mxC - mnC + 1) == (i + 1);
            sum += ans[i];
        }
        return sum;
    } else {
        vector<array<int, 3>> updates;
        //0 = row, 1 = column
        placeX[x[a]].erase(a);
        placeY[y[a]].erase(a);
        placeX[x[b]].erase(b);
        placeY[y[b]].erase(b);
        swap(x[a], x[b]);
        swap(y[a], y[b]);
        placeX[x[a]].insert(a);
        placeY[y[a]].insert(a);
        placeX[x[b]].insert(b);
        placeY[y[b]].insert(b);
        for (int i = 0; i < n; ++i) {
            updates.push_back({*placeX[i].begin(), 0, i});
        }
        for (int i = 0; i < m; ++i) {
            updates.push_back({*placeY[i].begin(), 1, i});
        }
        sort(updates.begin(), updates.end());
        vector<array<int, 3>> left;
        int mn[2] = {inf, inf};
        int mx[2] = {-inf, -inf};
        for (auto [k, tp, v] : updates) {
            if (upd(mx[tp], mn[tp], v)) {
                left.push_back({k, tp, v});
            }
        }
        sum = 0;
        mn[0] = mn[1] = inf;
        mx[0] = mx[1] = -inf;
        for (int i = 0; i < (int)left.size(); ++i) {
            auto [k, tp, v] = left[i];
            upd(mx[tp], mn[tp], v);
            if (mn[0] == inf || mn[1] == inf) {
                continue;
            }
            int val = (mx[0] - mn[0] + 1) * (mx[1] - mn[1] + 1);
            if (val < k + 1 || (i != (int)left.size() - 1 && left[i + 1][0] + 1 <= val)) {
                continue;
            }
            sum += 1;
        }
        return sum;
    }
}

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