Submission #600870

#	Time	Username	Problem	Language	Result	Execution time	Memory
600870		piOOE	Seats (IOI18_seats)	C++17	17 / 100	4097 ms	54932 KiB

seats

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

using namespace std;

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 = INT_MIN, Min = INT_MAX;
        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;

SegTree R, C;

void upd(int& mx, int & mn, int val) {
    mx = max(mx, val);
    mn = min(mn, val);
}

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);
    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]);
        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);
    }
    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;
}

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