← Real problems

ioi05p2

hardsegment-treeofflinecompressionStatement on DMOJ

CP Lang

33 lines0.3 spec
// ioi05p2 Mountain: rails 1..=n start flat; commands set the slope of a block of rails or ask how
// far a car with energy h gets (the last rail before the height first exceeds h). Offline: the
// command endpoints cut the track into stretches of one slope each; a segment tree over them
// keeps (rise, highest prefix, length) under "assign slope", and the query walks right while the
// highest prefix stays at most h, then divides inside the stretch where it breaks.
let n = read<1..=1_000_000_000>()
domain Rail = 1..=n
enum Cmd:
    @tag("I") Set(a: Rail, b: Rail, d: -1_000_000_000..=1_000_000_000)
    @tag("Q") Ask(h: 0..=1_000_000_000)
    @tag("E") End
let cmds = read_all<Cmd>(until: c => c == Cmd.End)
let (domain P, piece) = Rail.pieces(cuts: cmds.flat_map(c => if c is Cmd.Set(a, b, _): [a.l, b.r] else: []))
type Rise = (rise: Int, peak: Int, len: Int)
let track = Monoid<Rise>(id: (rise: 0, peak: 0, len: 0),
    op: (x, y) => (rise: x.rise + y.rise, peak: max(x.peak, x.rise + y.peak), len: x.len + y.len))
let slope = Action<Rise, ?Int>(id: None, compose: (old, new) => new ?? old,
    apply: (d, x, _) => if d is Some(v): (rise: v * x.len, peak: max(0, v * x.len), len: x.len) else: x,
    over: track)
var t = SegTree(track, [P] p => (rise: 0, peak: 0, len: piece[p].len), act: slope)
for c in cmds:
    match c:
        Set(a, b, d) => t.apply(piece.covering(a..=b), Some(d))
        End => continue
        Ask(h) =>
            let stop = t.right_while(P.cuts.first!, x => x.peak <= h)
            if stop == P.cuts.last!:
                print(n)
            else:
                let p = stop.r!
                let seg = t.get(p)
                let base = t.fold(..stop).rise
                print(Int(piece[p].first!.l) + (h - base) / (seg.rise / seg.len))

Accepted C++

177 lines · 1.54 s on the judge
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

constexpr int nlazy = INT_MIN, maxn = 1e9 + 5;

struct Node {
    int pref, sm;

    Node operator+(const Node& n) const {
        return {max(pref, sm + n.pref), sm + n.sm};
    }

    Node apply(int lazy, int l, int r) const {
        if (lazy == nlazy) {
            return *this;
        } else {
            int x = lazy * (r - l + 1);
            return {max(0, x), x};
        }
    }

    static Node from(int x) {
        return {max(0, x), x};
    }
};

struct N {
    Node v;
    int lazy, lc, rc;
} heap[(200 << 20) / sizeof(N)];
int root, hind = 1;

int alloc() {
    heap[hind].lazy = nlazy;
    return hind++;
}

void alloc(int& o) {
    if (!o) {
        o = alloc();
    }
}

void maintain(int o, int l, int r) {
    if (o) {
        auto& [v, lazy, lc, rc] = heap[o];
        v = (heap[lc].v + heap[rc].v).apply(lazy, l, r);
    }
}

void update(int& o, int l, int r, int ql, int qr, int x) {
    alloc(o);
    auto& [_, lazy, lc, rc] = heap[o];
    if (ql <= l && r <= qr) {
        lazy = x;
    } else {
        int mid = (l + r) / 2;
        alloc(lc);
        alloc(rc);
        if (lazy != nlazy) {
            heap[lc].lazy = heap[rc].lazy = lazy;
            lazy = nlazy;
        }
        if (ql <= mid) {
            update(lc, l, mid, ql, qr, x);
        } else {
            maintain(lc, l, mid);
        }
        if (mid < qr) {
            update(rc, mid + 1, r, ql, qr, x);
        } else {
            maintain(rc, mid + 1, r);
        }
    }
    maintain(o, l, r);
}

void update(int l, int r, int x) {
    update(root, 0, maxn, l, r, x);
}

Node query(int o, int l, int r, int ql, int qr, int clazy) {
    if (!o) {
        return Node::from(0).apply(clazy, max(ql, l), min(qr, r));
    }
    auto& [v, lazy, lc, rc] = heap[o];
    if (ql <= l && r <= qr) {
        return v.apply(clazy, l, r);
    }
    if (clazy == nlazy) {
        clazy = lazy;
    }
    int mid = (l + r) / 2;
    if (ql <= mid) {
        if (mid < qr) {
            return query(lc, l, mid, ql, qr, clazy) +
                   query(rc, mid + 1, r, ql, qr, clazy);
        }
        return query(lc, l, mid, ql, qr, clazy);
    }
    return query(rc, mid + 1, r, ql, qr, clazy);
}

Node query(int l, int r) {
    return query(root, 0, maxn, l, r, nlazy);
}

void solve() {
//    {
//        update(0, 3, 2);
//        dbg(query(0, 2).pref);
//        return;
//    }
    int n;
    cin >> n;
    while (true) {
        char t;
        cin >> t;
        if (t == 'I') {
            int l, r, x;
            cin >> l >> r >> x;
            l--;
            r--;
            update(l, r, x);
        } else if (t == 'Q') {
            int x;
            cin >> x;
            int l = -1, r = n - 1;
            while (l < r) {
                int mid = (l + r + 1) / 2;
                if (query(0, mid).pref <= x) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            cout << l + 1 << endl;
        } else {
            break;
        }
    }
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cin.exceptions(ios::failbit);
    solve();
}