Submission #991516

#	Time	Username	Problem	Language	Result	Execution time	Memory
991516		shiomusubi496	Seats (IOI18_seats)	C++17	31 / 100	4041 ms	57172 KiB

seats

#include "seats.h"

#include <bits/stdc++.h>

namespace SOLVE {

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); --i)
#define all(v) begin(v), end(v)

using namespace std;

using ll = long long;

template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; }
template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; }



constexpr int infty = 1e9;

template<class M>
class SegmentTree {
    using T = typename M::T;
    int n, ori;
    vector<T> dat;

public:
    void init(int n_) {
        ori = n_;
        n = 1;
        while (n < n_) n *= 2;
        dat.assign(2 * n, M::id());
    }
    void set(int k, T x) {
        k += n;
        dat[k] = x;
        while (k > 1) {
            k /= 2;
            dat[k] = M::op(dat[k * 2], dat[k * 2 + 1]);
        }
    }
    T prod(int l, int r) const {
        T sml = M::id(), smr = M::id();
        l += n; r += n;
        while (l < r) {
            if (l & 1) sml = M::op(sml, dat[l++]);
            if (r & 1) smr = M::op(dat[--r], smr);
            l >>= 1; r >>= 1;
        }
        return M::op(sml, smr);
    }
    template<class F>
    int max_right(int k, F&& f) const {
        if (k == ori) return ori;
        k += n;
        T sm = M::id();
        do {
            while (k % 2 == 0) k >>= 1;
            if (!f(M::op(sm, dat[k]))) {
                while (k < n) {
                    k = 2 * k;
                    if (f(M::op(sm, dat[k]))) {
                        sm = M::op(sm, dat[k]);
                        ++k;
                    }
                }
                return k - n;
            }
            sm = M::op(sm, dat[k]);
            ++k;
        } while ((k & -k) != k);
        return ori;
    }
};

struct Max {
    using T = int;
    static T id() { return -infty; }
    static T op(T a, T b) { return max(a, b); }
};
struct Min {
    using T = int;
    static T id() { return infty; }
    static T op(T a, T b) { return min(a, b); }
};

int H, W;
vector<int> R, C;
SegmentTree<Min> mR, mC;
SegmentTree<Max> MR, MC;

}

void give_initial_chart(int H_, int W_, std::vector<int> R_, std::vector<int> C_) {
    using namespace SOLVE;

    H = H_; W = W_;
    R = R_; C = C_;
    mR.init(H * W);
    MR.init(H * W);
    mC.init(H * W);
    MC.init(H * W);
    rep (i, H * W) {
        mR.set(i, R[i]);
        MR.set(i, R[i]);
        mC.set(i, C[i]);
        MC.set(i, C[i]);
    }
}

int swap_seats(int a, int b) {
    using namespace SOLVE;

    if (a > b) swap(a, b);

    swap(R[a], R[b]);
    swap(C[a], C[b]);
    mR.set(a, R[a]); mR.set(b, R[b]);
    MR.set(a, R[a]); MR.set(b, R[b]);
    mC.set(a, C[a]); mC.set(b, C[b]);
    MC.set(a, C[a]); MC.set(b, C[b]);

    int mr = R[0], Mr = R[0];
    int mc = C[0], Mc = C[0];
    int ans = 1;
    while (mr > 0 || Mr < H - 1 || mc > 0 || Mc < W - 1) {
        int nxt = min({
            mR.max_right(0, [&](int x) { return x >= mr; }),
            MR.max_right(0, [&](int x) { return x <= Mr; }),
            mC.max_right(0, [&](int x) { return x >= mc; }),
            MC.max_right(0, [&](int x) { return x <= Mc; })
        });
        if (nxt == (Mr - mr + 1) * (Mc - mc + 1)) ++ans;
        chmin(mr, R[nxt]);
        chmax(Mr, R[nxt]);
        chmin(mc, C[nxt]);
        chmax(Mc, C[nxt]);
    }
    return ans;
}

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