제출 #709827

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
709827		Cyanmond	자리 배치 (IOI18_seats)	C++17	33 / 100	1183 ms	73124 KiB

seats

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

template <class M>
class LazySegmentTree {
    using T = typename M::T;
    using L = typename M::L;
    int n, size, logn;
    std::vector<T> data;
    std::vector<L> lazy;

    void update(int i) {
        data[i] = M::op(data[2 * i], data[2 * i + 1]);
    }

    void all_apply(int i, const L &f) {
        data[i] = M::map(f, data[i]);
        if (i < size) lazy[i] = M::composite(f, lazy[i]);
    }

    void push(int i) {
        all_apply(2 * i, lazy[i]);
        all_apply(2 * i + 1, lazy[i]);
        lazy[i] = M::id();
    }

    public:
    LazySegmentTree() {}
    LazySegmentTree(const std::vector<T> &vec) {
        n = (int)vec.size();
        logn = 1;
        while ((1 << logn) < n) ++logn;
        size = 1 << logn;
        data.assign(2 * size, M::e());
        std::copy(vec.begin(), vec.end(), data.begin() + size);
        for (int i = size - 1; i >= 1; --i) update(i);
        lazy.assign(size, M::id());
    }

    void apply(int l, int r, const L &f) {
        l += size;
        r += size;
        for (int d = logn; d >= 1; --d) {
            if (((l >> d) << d) != l) push(l >> d);
            if (((r >> d) << d) != r) push((r - 1) >> d);
        }
        int l2 = l, r2 = r;
        while (l < r) {
            if (l & 1) all_apply(l++, f);
            if (r & 1) all_apply(--r, f);
            l /= 2;
            r /= 2;
        }
        l = l2;
        r = r2;
        for (int d = 1; d <= logn; ++d) {
            if (((l >> d) << d) != l) update(l >> d);
            if (((r >> d) << d) != r) update((r - 1) >> d);
        }
    }

    T fold(int l, int r) {
        l += size;
        r += size;
        for (int d = logn; d >= 1; --d) {
            if (((l >> d) << d) != l) push(l >> d);
            if (((r >> d) << d) != r) push((r - 1) >> d);
        }
        T pl = M::e(), pr = M::e();
        while (l < r) {
            if (l & 1) pl = M::op(pl, data[l++]);
            if (r & 1) pr = M::op(data[--r], pr);
            l /= 2;
            r /= 2;
        }
        return M::op(pl, pr);
    }
};

constexpr int inf = 1 << 30;

struct MCountMin {
    struct T {
        int mn, cnt;
    };
    static T op(T a, T b) {
        if (a.mn == b.mn) return {a.mn, a.cnt + b.cnt};
        return a.mn < b.mn ? a : b;
    }
    static T e() {
        return {inf, 0};
    }
    struct L {
        int ad;
    };
    static T map(L a, T b) {
        return {b.mn + a.ad, b.cnt};
    }
    static L composite(L a, L b) {
        return {a.ad + b.ad};
    }
    static L id() {
        return {0};
    } 
};

template <class M>
class SegmentTree {
    using T = typename M::T;
    int n, size;
    std::vector<T> data;

    void update(int i) {
        data[i] = M::op(data[2 * i], data[2 * i + 1]);
    }

    public:
    SegmentTree() {}
    SegmentTree(const std::vector<T> &vec) {
        n = (int)vec.size();
        size = 1;
        while (size < n) {
            size *= 2;
        }
        data.assign(2 * size, M::e());
        std::copy(vec.begin(), vec.end(), data.begin() + size);
        for (int i = size - 1; i >= 1; --i) update(i);
    }

    void set(int i, const T &v) {
        i += size;
        data[i] = v;
        while (i != 1) {
            i /= 2;
            update(i);
        }
    }

    T fold(int l, int r) {
        T pl = M::e(), pr = M::e();
        for (l += size, r += size; l < r; l /= 2, r /= 2) {
            if (l & 1) pl = M::op(pl, data[l++]);
            if (r & 1) pr = M::op(data[--r], pr);
        }
        return M::op(pl, pr);
    }
};


struct MonoidMinMax {
    using T = std::pair<int, int>;
    static T op(const T &a, const T &b) {
        return {std::min(a.first, b.first), std::max(a.second, b.second)};
    }
    static T e() {
        return {inf, -1};
    }
};

int H, W;
std::vector<int> R, C;
// SegmentTree<MonoidMinMax> rowSeg, colSeg;
LazySegmentTree<MCountMin> seg;
std::vector<std::set<int>> rowIds, colIds;
std::vector<std::pair<int, bool>> firstIds;
std::vector<int> times;

void give_initial_chart(int h, int w, std::vector<int> r, std::vector<int> c) {
    H = h;
    W = w;
    R = r;
    C = c;
    assert(H == 1);
    times.resize(W);
    for (int i = 0; i < W; ++i) {
        times[c[i]] = i;
    }
    seg = LazySegmentTree<MCountMin>(std::vector<typename MCountMin::T>(W, {0, 1}));
    for (int i = -1; i < W; ++i) {
        int x = i == -1 ? W : times[i], y = i == W - 1 ? W : times[i + 1];
        if (x > y) std::swap(x, y);
        seg.apply(x, y, {1});
    }

    /*
    rowSeg = SegmentTree<MonoidMinMax>(rInit);
    colSeg = SegmentTree<MonoidMinMax>(cInit);
    rowIds.resize(H);
    colIds.resize(W);
    for (int i = 0; i < H * W; ++i) {
        if (colIds[C[i]].empty()) {
            firstIds.push_back({i, false});
        }
        colIds[C[i]].insert(i);
        if (rowIds[R[i]].empty()) {
            firstIds.push_back({i, true});
        }
        rowIds[R[i]].insert(i);
    }
    */
}

void updRow(int i, int v, bool b) {
    if (not rowIds[i].empty()) {
        int mi = *rowIds[i].begin();
        auto itr = std::find(firstIds.begin(), firstIds.end(), std::make_pair(mi, true));
        firstIds.erase(itr);
    }

    if (b) rowIds[i].insert(v);
    else rowIds[i].erase(v);

    if (rowIds[i].empty()) return;
    int mi = *rowIds[i].begin();
    auto itr = std::lower_bound(firstIds.begin(), firstIds.end(), std::make_pair(mi, true));
    firstIds.insert(itr, {mi, true});
}
void updCol(int i, int v, bool b) {
    if (not colIds[i].empty()) {
        int mi = *colIds[i].begin();
        auto itr = std::find(firstIds.begin(), firstIds.end(), std::make_pair(mi, false));
        firstIds.erase(itr);
    }

    if (b) colIds[i].insert(v);
    else colIds[i].erase(v);

    if (colIds[i].empty()) return;
    int mi = *colIds[i].begin();
    auto itr = std::lower_bound(firstIds.begin(), firstIds.end(), std::make_pair(mi, false));
    firstIds.insert(itr, {mi, false});
}

void eraseI(int i) {
    int x = i == -1 ? W : times[i], y = i == W - 1 ? W : times[i + 1];
    if (x > y) std::swap(x, y);
    seg.apply(x, y, {-1});
}
void addI(int i) {
    int x = i == -1 ? W : times[i], y = i == W - 1 ? W : times[i + 1];
    if (x > y) std::swap(x, y);
    seg.apply(x, y, {1});
}

int swap_seats(int a, int b) {
    // upd
    /*
    updRow(R[a], a, false);
    updCol(C[a], a, false);
    updRow(R[b], b, false);
    updCol(C[b], b, false);
    updRow(R[a], b, true);
    updCol(C[a], b, true);
    updRow(R[b], a, true);
    updCol(C[b], a, true);
    rowSeg.set(a, std::make_pair(R[b], R[b]));
    rowSeg.set(b, std::make_pair(R[a], R[a]));
    colSeg.set(a, std::make_pair(C[b], C[b]));
    colSeg.set(b, std::make_pair(C[a], C[a]));
    */

    eraseI(C[a]);
    eraseI(C[a] - 1);
    eraseI(C[b]);
    eraseI(C[b] - 1);
    std::swap(times[C[a]], times[C[b]]);
    // std::swap(R[a], R[b]);
    std::swap(C[a], C[b]);
    addI(C[a]);
    addI(C[a] - 1);
    addI(C[b]);
    addI(C[b] - 1);
    const auto res = seg.fold(0, W);
    return res.cnt;

    // calc
    /*
    int answer = 0;
    int last = 0;
    for (const auto [i, b] : firstIds) {
        // at i - 1
        if (last == i) {
            continue;
        }
        const auto x = rowSeg.fold(0, i), y = colSeg.fold(0, i);
        if ((x.second - x.first + 1) * (y.second - y.first + 1) == i) {
            ++answer;
        }
        last = i;
    }
    ++answer;
    */
}

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