Submission #991397

#	Time	Username	Problem	Language	Result	Execution time	Memory
991397		Forested	자리 배치 (IOI18_seats)	C++17	33 / 100	781 ms	56768 KiB

seats

#include <bits/stdc++.h>
#define OVERRIDE4(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, l, r) for (i32 i = (i32)(l); i < (i32)(r); ++i)
#define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER2(i, n) for (i32 i = (i32)(n)-1; i >= 0; --i)
#define PER3(i, l, r) for (i32 i = (i32)(r)-1; i >= (i32)(l); --i)
#define PER(...) OVERRIDE4(__VA_ARGS__, PER3, PER2)(__VA_ARGS__)
#define LEN(x) (i32)(x).size()
#define ALL(x) begin(x), end(x)
using namespace std;
using i32 = int;
using i64 = long long;
template <typename T>
using V = vector<T>;
template <typename T>
bool chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

#include "seats.h"

constexpr i32 INF = 1001001001;

i32 ceil_log2(i32 n) {
    i32 l = 0;
    while ((1 << l) < n) {
        ++l;
    }
    return l;
}

class RangeAddCountMin {
    using Value = pair<i32, i32>;
    using Func = i32;
    static Value id() { return Value(INF, 0); }
    static Value op(Value x, Value y) {
        i32 mn = min(x.first, y.first);
        i32 cnt = 0;
        if (x.first == mn) {
            cnt += x.second;
        }
        if (y.first == mn) {
            cnt += y.second;
        }
        return Value(mn, cnt);
    }
    static Func func_id() { return 0; }
    static Func composite(Func f, Func g) { return f + g; }
    static Value apply(Func f, Value x) { return Value(f + x.first, x.second); }

    i32 lg, n;
    V<Value> val;
    V<Func> fun;

    void push(i32 idx) {
        if (idx < n) {
            REP(i, 2) {
                val[2 * idx + i] = apply(fun[idx], val[2 * idx + i]);
                fun[2 * idx + i] = composite(fun[idx], fun[2 * idx + i]);
            }
            fun[idx] = func_id();
        }
    }

    void push_(i32 idx) {
        PER(i, 1, lg + 1) { push(idx >> i); }
    }

    void apply_(i32 idx, Func f) {
        val[idx] = apply(f, val[idx]);
        fun[idx] = composite(f, fun[idx]);
    }

    void update(i32 idx) {
        if (idx < n) {
            val[idx] = op(val[2 * idx], val[2 * idx + 1]);
        }
    }

public:
    RangeAddCountMin() = default;
    RangeAddCountMin(i32 _n)
        : lg(ceil_log2(_n)),
          n(1 << lg),
          val(2 * n, id()),
          fun(2 * n, func_id()) {
        REP(i, n, 2 * n) {
            val[i] = Value(0, 1);
        }
        PER(i, 1, n) {
            val[i] = op(val[2 * i], val[2 * i + 1]);
        }
    }

    void range_add(i32 l, i32 r, i32 v) {
        if (l == r) {
            return;
        }
        //cout << l << ' ' << r << ' ' << v << '\n';
        l += n;
        r += n;
        push_(l);
        push_(r - 1);
        i32 l_ = l;
        i32 r_ = r;
        while (l < r) {
            if (l & 1) {
                apply_(l++, v);
            }
            if (r & 1) {
                apply_(--r, v);
            }
            l /= 2;
            r /= 2;
        }
        REP(i, lg + 1) {
            if ((l_ >> i << i) != l_) {
                update(l_ >> i);
            }
            if ((r_ >> i << i) != r_) {
                update(r_ >> i);
            }
        }
        /*REP(i, 1, 2 * n) {
            cout << "(" << val[i].first << ", " << val[i].second << ")" << " \n"[i + 1 == 2 * n];
        }
        REP(i, 1, 2 * n) {
            cout << fun[i] << " \n"[i + 1 == 2 * n];
        }*/
    }

    pair<i32, i32> get_min_and_cnt(i32 l, i32 r) {
        if (l == r) {
            return id();
        }
        l += n;
        r += n;
        push_(l);
        push_(r - 1);
        Value ret = id();
        while (l < r) {
            if (l & 1) {
                ret = op(ret, val[l++]);
            }
            if (r & 1) {
                ret = op(ret, val[--r]);
            }
            l /= 2;
            r /= 2;
        }
        return ret;
    }
};

i32 h, w;
V<i32> r, c;

V<i32> pos;
V<i32> ord;

RangeAddCountMin ds;

void process(i32 i, i32 wt) {
    if (i == -1) {
        ds.range_add(ord[0], w, wt);
    } else if (i == w - 1) {
        ds.range_add(ord[w - 1], w, wt);
    } else {
        i32 x = ord[i], y = ord[i + 1];
        if (x > y) {
            swap(x, y);
        }
        ds.range_add(x, y, wt);
    }
}

void give_initial_chart(i32 _h, i32 _w, V<i32> _r, V<i32> _c) {
    h = _h;
    w = _w;
    r = _r;
    c = _c;

    assert(h == 1);
    pos = c;
    ord.resize(w);
    REP(i, w) { ord[pos[i]] = i; }
    ds = RangeAddCountMin(w);
    REP(i, -1, w) {
        process(i, 1);
    }
}

i32 swap_seats(i32 a, i32 b) {
    if (pos[a] > pos[b]) {
        swap(a, b);
    }
    bool adj = pos[b] == pos[a] + 1;
    process(pos[a] - 1, -1);
    process(pos[a], -1);
    if (!adj) process(pos[b] - 1, -1);
    process(pos[b], -1);
    swap(ord[pos[a]], ord[pos[b]]);
    swap(pos[a], pos[b]);
    process(pos[b] - 1, 1);
    process(pos[b], 1);
    if (!adj) process(pos[a] - 1, 1);
    process(pos[a], 1);
    auto ret = ds.get_min_and_cnt(0, w);
    return ret.second;
}

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