Submission #991414

#	Time	Username	Problem	Language	Result	Execution time	Memory
991414		Forested	Seats (IOI18_seats)	C++17	5 / 100	4086 ms	56660 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 Segtree {
    using Value = pair<i32, i32>;
    static Value id() {
        return Value(INF, -INF);
    }
    static Value op(Value x, Value y) {
        return Value(min(x.first, y.first), max(x.second, y.second));
    }
    i32 n;
    V<Value> dat;
public:
    Segtree() = default;
    Segtree(i32 _n) : n(1 << ceil_log2(_n)), dat(2 * n, id()) {}
    void update(i32 idx, i32 val) {
        idx += n;
        dat[idx] = Value(val, val);
        idx /= 2;
        while (idx > 0) {
            dat[idx] = op(dat[2 * idx], dat[2 * idx + 1]);
            idx /= 2;
        }
    }
    Value getminmax(i32 l, i32 r) {
        l += n;
        r += n;
        Value ret = id();
        while (l < r) {
            if (l & 1) {
                ret = op(ret, dat[l++]);
            }
            if (r & 1) {
                ret = op(ret, dat[--r]);
            }
            l /= 2;
            r /= 2;
        }
        return ret;
    }
    i32 go(i32 l) {
        Value cur = getminmax(0, l);
        i32 ok = l, ng = n + 1;
        while (ng - ok > 1) {
            i32 mid = (ok + ng) / 2;
            if (getminmax(0, mid) == cur) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        return ok;
    }
};

i32 h, w;
V<i32> r, c;
Segtree segr, segc;

void give_initial_chart(i32 _h, i32 _w, V<i32> _r, V<i32> _c) {
    h = _h;
    w = _w;
    r = _r;
    c = _c;
    
    assert(h <= 1000 && w <= 1000);
    segr = Segtree(h * w);
    segc = Segtree(h * w);
    REP(i, h * w) {
        segr.update(i, r[i]);
        segc.update(i, c[i]);
    }
}

i32 swap_seats(i32 a, i32 b) {
    if (a > b) {
        swap(a, b);
    }
    swap(r[a], r[b]);
    swap(c[a], c[b]);
    segc.update(a, c[a]);
    segr.update(a, r[a]);
    segc.update(b, c[b]);
    segr.update(b, r[b]);
    V<i32> cands;
    {
        i32 l = 0;
        while (l < h * w) {
            i32 r = segc.go(l + 1);
            cands.push_back(r - 1);
            l = r;
        }
    }
    {
        i32 l = 0;
        while (l < h * w) {
            i32 r = segr.go(l + 1);
            cands.push_back(r - 1);
            l = r;
        }
    }
    cands.push_back(h * w - 1);
    sort(ALL(cands));
    cands.erase(unique(ALL(cands)), cands.end());
    i32 ans = 0;
    for (i32 k : cands) {
        auto [u, d] = segc.getminmax(0, k + 1);
        auto [l, r] = segr.getminmax(0, k + 1);
        if ((d - u + 1) * (r - l + 1) == k + 1) {
            ++ans;
        }
    }
    return ans;
}

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