Submission #995514

#	Time	Username	Problem	Language	Result	Execution time	Memory
995514		Forested	Meetings (IOI18_meetings)	C++17	60 / 100	1164 ms	66644 KiB

meetings

#include <bits/stdc++.h>
using namespace std;
using i32 = int;
using i64 = long long;
template <typename T>
using V = vector<T>;
template <typename T>
using VV = V<V<T>>;
#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 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 REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER(...) OVERRIDE4(__VA_ARGS__, PER3, PER2)(__VA_ARGS__)
#define LEN(x) (i32)size(x)
#define ALL(x) begin(x), end(x)
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 "meetings.h"

constexpr i32 INF = 1001001001;
constexpr i64 INF64 = 3003003003003003003;

i64 solve_naive(V<i64> h) {
    i32 n = LEN(h);
    V<i64> cost(n, 0);
    V<pair<i64, i32>> stc;
    stc.emplace_back(INF, -1);
    i64 cur = 0;
    REP(i, n) {
        while (stc.back().first <= h[i]) {
            i64 v;
            i32 j;
            tie(v, j) = stc.back();
            stc.pop_back();
            cur -= v * (j - stc.back().second);
        }
        cur += (i64)h[i] * (i - stc.back().second);
        stc.emplace_back(h[i], i);
        cost[i] += cur;
    }
    stc.clear();
    stc.emplace_back(INF, n);
    cur = 0;
    PER(i, n) {
        while (stc.back().first <= h[i]) {
            i64 v;
            i32 j;
            tie(v, j) = stc.back();
            stc.pop_back();
            cur -= v * (stc.back().second - j);
        }
        cur += (i64)h[i] * (stc.back().second - i);
        stc.emplace_back(h[i], i);
        cost[i] += cur;
    }
    REP(i, n) {
        cost[i] -= h[i];
    }
    i64 mn = INF64;
    REP(i, n) {
        chmin(mn, cost[i]);
    }
    return mn;
}

struct Segment {
    i32 len;
    i64 lmax, rmax, cost;
    Segment() : len(0), lmax(0), rmax(0), cost(0) {}
    Segment(i64 x) : len(1), lmax(x), rmax(x), cost(x) {}
};

struct Data {
    V<Segment> segs;
};

void compress(V<Segment> &segs) {
    V<Segment> ret;
    for (const Segment &seg : segs) {
        if (!ret.empty() && ret.back().lmax == seg.lmax && ret.back().rmax == seg.rmax) {
            ret.back().len += seg.len;
            chmin(ret.back().cost, seg.cost);
        } else {
            ret.push_back(seg);
        }
    }
    segs = ret;
}

Data id() {
    return Data{V<Segment>(0)};
}

Data op(Data x, Data y) {
    if (x.segs.empty()) {
        return y;
    }
    if (y.segs.empty()) {
        return x;
    }
    V<pair<i64, i32>> ll;
    i64 sum = 0;
    REP(i, LEN(x.segs)) {
        Segment seg = x.segs[i];
        sum += seg.rmax * seg.len;
        ll.emplace_back(seg.rmax, seg.len);
    }
    i32 pct = 0;
    REP(i, LEN(y.segs)) {
        Segment &seg = y.segs[i];
        while (!ll.empty() && ll.back().first <= seg.lmax) {
            sum -= ll.back().first * ll.back().second;
            pct += ll.back().second;
            ll.pop_back();
        }
        seg.cost += pct * seg.lmax + sum;
    }
    ll.clear();
    sum = 0;
    PER(i, LEN(y.segs)) {
        Segment seg = y.segs[i];
        sum += seg.lmax * seg.len;
        ll.emplace_back(seg.lmax, seg.len);
    }
    pct = 0;
    PER(i, LEN(x.segs)) {
        Segment &seg = x.segs[i];
        while (!ll.empty() && ll.back().first <= seg.rmax) {
            sum -= ll.back().first * ll.back().second;
            pct += ll.back().second;
            ll.pop_back();
        }
        seg.cost += pct * seg.rmax + sum;
    }
    i64 rmax = y.segs[0].rmax;
    PER(i, LEN(x.segs)) {
        chmax(rmax, x.segs[i].rmax);
        x.segs[i].rmax = rmax;
    }
    i64 lmax = x.segs.back().lmax;
    REP(i, LEN(y.segs)) {
        chmax(lmax, y.segs[i].lmax);
        y.segs[i].lmax = lmax;
    }
    REP(i, LEN(y.segs)) {
        x.segs.push_back(y.segs[i]);
    }
    compress(x.segs);
    return x;
}

i32 ceil_pow2(i32 n) {
    i32 k = 1;
    while (k < n) {
        k *= 2;
    }
    return k;
}

class Segtree {
    i32 n;
    V<Data> dat;
    
public:
    Segtree(i32 _n) : n(ceil_pow2(_n)), dat(2 * n, id()) {}
    
    void update(i32 idx, Data d) {
        idx += n;
        dat[idx] = d;
        idx /= 2;
        while (idx > 0) {
            dat[idx] = op(dat[2 * idx], dat[2 * idx + 1]);
            idx /= 2;
        }
    }
    
    Data prod(i32 l, i32 r) const {
        l += n;
        r += n;
        Data lp = id(), rp = id();
        while (l < r) {
            if (l & 1) {
                lp = op(lp, dat[l++]);
            }
            if (r & 1) {
                rp = op(dat[--r], rp);
            }
            l /= 2;
            r /= 2;
        }
        return op(lp, rp);
    }
};

V<i64> minimum_costs(V<i32> _h, V<i32> l, V<i32> r) {
    i32 n = LEN(_h);
    i32 q = LEN(l);
    V<i64> h(n);
    REP(i, n) {
        h[i] = _h[i];
    }
    REP(i, q) {
        ++r[i];
    }
    
    if (n <= 5000 && q <= 5000) {
        V<i64> ret(q);
        REP(i, q) {
            ret[i] = solve_naive(V<i64>(h.begin() + l[i], h.begin() + r[i]));
        }
        return ret;
    }
    assert(*max_element(ALL(h)) <= 20);
    
    Segtree seg(n);
    REP(i, n) {
        Segment tmp(h[i]);
        seg.update(i, Data{V<Segment>({tmp})});
    }
    V<i64> pct(q);
    REP(i, q) {
        Data ret = seg.prod(l[i], r[i]);
        i64 ans = INF64;
        for (const Segment &seg : ret.segs) {
            chmin(ans, seg.cost);
        }
        pct[i] = ans;
    }
    return pct;
}

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 0 / 40