← Real problems

cco20p5

unratedStatement on DMOJ

CP Lang

55 lines0.3 spec
// CCO 2020 "Interval Collection": add and remove intervals; after each change
// print the shortest span over all sets whose intersection is smallest. If
// two intervals are disjoint the intersection is empty and the best span is the
// closest disjoint pair, kept by a segment tree over coordinates: per point the
// largest left end of intervals ending there and the smallest right end of
// intervals starting there. Otherwise the intersection is fixed by the
// smallest right end and the largest left end.
enum Op = Add(l: X, r: X) | Remove(l: X, r: X)
domain X = 1..=1e6

struct Gap(end_l: ?X, start_r: ?X, span: ?Int)

fn join(a: Gap, b: Gap) -> Gap:
    let across = if a.end_l is Some(l) and b.start_r is Some(r): Some(Int(r) - Int(l)) else: None
    Gap(
        end_l: [a.end_l, b.end_l].filter_map(x => x).max(),
        start_r: [a.start_r, b.start_r].filter_map(x => x).min(),
        span: [a.span, b.span, across].filter_map(x => x).min(),
    )

let q = read<1..=5e5>()
var gaps = SegTree(join, [X] _ => Gap(end_l: None, start_r: None, span: None))
var lefts_ending = Map<X, SortedBag<X>>()
var rights_starting = Map<X, SortedBag<X>>()
var by_end = SortedBag<(r: X, l: Desc<X>)>()
var by_start = SortedBag<(l: Desc<X>, r: X)>()
var lens = SortedBag<Int>()

fn refresh(l: X, r: X):
    let at_r = gaps.get(r)
    gaps.set(r, Gap(end_l: lefts_ending.get(r).and_then(b => b.last), start_r: at_r.start_r, span: None))
    let at_l = gaps.get(l)
    gaps.set(l, Gap(end_l: at_l.end_l, start_r: rights_starting.get(l).and_then(b => b.first), span: None))

for op in read<[q]Op>():
    match op:
        Add(l, r) =>
            lefts_ending.get_or_insert(r).add(l)
            rights_starting.get_or_insert(l).add(r)
            by_end.add((r: r, l: desc(l)))
            by_start.add((l: desc(l), r: r))
            lens.add(Int(r) - Int(l))
            refresh(l, r)
        Remove(l, r) =>
            lefts_ending[r].remove(l)
            rights_starting[l].remove(r)
            by_end.remove((r: r, l: desc(l)))
            by_start.remove((l: desc(l), r: r))
            lens.remove(Int(r) - Int(l))
            refresh(l, r)
    if gaps.fold(X.range).span is Some(s):
        print(s)
    else:
        let (a, b) = (by_end.first!, by_start.first!)
        print(if Int(a.r) == Int(b.l.x): lens.first! else: Int(b.r) - Int(a.l.x))

Accepted C++

299 lines · 163.98 s on the judge
#pragma GCC optimize("Ofast")

#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 dbg(...)
#define cerr   \
	if (false) \
	cerr
#endif

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

template <typename T>
struct Ncmp {
	T t;

	template <typename A, typename B>
	bool operator()(const A& a, const B& b) const {
		return t(b, a);
	}
};

template <typename T, typename Cmp = less<T>>
using min_pq = priority_queue<T, vector<T>, Ncmp<Cmp>>;

struct chash {
	uint64_t operator()(const pair<int, int>& x) const {
		uint64_t ans = (uint64_t(x.first) << 32) ^ x.second;
		ans ^= ans << 17;
		ans ^= ans >> 13;
		ans ^= ans << 19;
		ans ^= ans >> 21;
		return ans;
	}
};

const int maxn = 1 << 20, tmaxn = maxn << 1, qmaxn = 1 << 19;

template <typename T, int N>
struct avec {
	int ptr = 0;
	T arr[N];

	avec() {}

	void push_back() {
		ptr++;
	}

	void push_back(const T& t) {
		arr[ptr++] = t;
	}

	T& operator[](int ind) {
		return arr[ind];
	}

	T& back() {
		return arr[ptr - 1];
	}

	void pop_back() {
		ptr--;
	}
};

struct DS1 {
	int v[maxn + 1] {};
	avec<avec<int, 20>, qmaxn> c;

	void update(int ind, int x) {
		c.push_back();
		c.back().ptr = 0;
		c.back().push_back(ind);
		while (ind <= maxn) {
			c.back().push_back(v[ind]);
			v[ind] = max(v[ind], x);
			ind += ind & -ind;
		}
	}

	int query(int ind) const {
		int ans = 0;
		while (ind > 0) {
			ans = max(ans, v[ind]);
			ind -= ind & -ind;
		}
		if (!ans) {
			return -1e9;
		}
		return ans;
	}

	void rollback() {
		auto& x = c.back();
		int ind = x[0], ptr = 1;
		while (ind <= maxn) {
			v[ind] = x[ptr++];
			ind += ind & -ind;
		}
		c.pop_back();
	}
};

struct DS2 {
	DS1 ds;
	int ans = 1e9;
	vector<int> ansc;

	void insert(int l, int r) {
		ansc.push_back(ans);
		ans = min(ans, r - ds.query(l));
		ds.update(r, l);
	}

	int query() const {
		return ans;
	}

	void rollback() {
		ds.rollback();
		ans = ansc.back();
		ansc.pop_back();
	}
};

struct DS3 {
	DS2 ds1, ds2;

	void insert(int l, int r) {
		ds1.insert(l, r);
		ds2.insert(maxn - r - 1, maxn - l - 1);
	}

	int query() const {
		return min(ds1.query(), ds2.query());
	}

	void rollback() {
		ds1.rollback();
		ds2.rollback();
	}
};

struct cmp1 {
	bool operator()(const pair<int, int>& a, const pair<int, int>& b) const {
		if (a.second == b.second) {
			return a.first > b.first;
		}
		return a.second < b.second;
	}

	bool operator()(const pair<pair<int, int>, int>& a, const pair<pair<int, int>, int>& b) const {
		return (*this)(a.first, b.first);
	}
};

struct cmp2 {
	bool operator()(const pair<int, int>& a, const pair<int, int>& b) const {
		if (a.first == b.first) {
			return a.second < b.second;
		}
		return a.first > b.first;
	}

	bool operator()(const pair<pair<int, int>, int>& a, const pair<pair<int, int>, int>& b) const {
		return (*this)(a.first, b.first);
	}
};

int q;
vector<pair<int, int>> st[qmaxn << 1];
int qans[qmaxn];

void update(int o, int l, int r, int ql, int qr, const pair<int, int>& x) {
	if (ql <= l && r <= qr) {
		st[o].push_back(x);
	} else {
		int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
		if (ql <= mid) {
			update(lc, l, mid, ql, qr, x);
		}
		if (mid < qr) {
			update(rc, mid + 1, r, ql, qr, x);
		}
	}
}

void update(int l, int r, const pair<int, int>& x) {
	update(1, 0, q - 1, l, r, x);
}

DS3 ds;
void solve(int o, int l, int r) {
	for (auto& [cl, cr] : st[o]) {
		dbg("+", cl, cr);
		ds.insert(cl, cr);
	}
	if (l == r) {
		dbg("Q", l);
		qans[l] = ds.query();
	} else {
		int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
		solve(lc, l, mid);
		solve(rc, mid + 1, r);
	}
	for (int i = 0; i < sz(st[o]); i++) {
		dbg("-");
		ds.rollback();
	}
}

void solve() {
	cin >> q;
	tuple<char, int, int> arr[q];
	for (auto& [c, l, r] : arr) {
		cin >> c >> l >> r;
	}
	__gnu_pbds::gp_hash_table<pair<int, int>, vector<int>, chash> inds;
	int back[q];
	for (int i = 0; i < q; i++) {
		auto& [c, l, r] = arr[i];
		if (c == 'A') {
			inds[{l, r}].push_back(i);
		} else {
			auto& x = inds[{l, r}];
			dbg(x.back(), i - 1);
			back[i] = x.back();
			update(x.back(), i - 1, {l, r});
			x.pop_back();
		}
	}
	for (auto& [k, v] : inds) {
		for (auto& a : v) {
			update(a, q - 1, k);
		}
	}
	solve(1, 0, q - 1);
	min_pq<pair<pair<int, int>, int>, cmp1> s1;
	min_pq<pair<pair<int, int>, int>, cmp2> s2;
	min_pq<pair<int, int>> opt;
	bool vis[q] {};
	for (int i = 0; i < q; i++) {
		auto& [c, l, r] = arr[i];
		if (c == 'A') {
			s1.push({{l, r}, i});
			s2.push({{l, r}, i});
			opt.emplace(r - l, i);
		} else {
			vis[back[i]] = true;
		}
		while (vis[s1.top().second]) {
			s1.pop();
		}
		while (vis[s2.top().second]) {
			s2.pop();
		}
		while (vis[opt.top().second]) {
			opt.pop();
		}
		pair<int, int> ans = {opt.top().first, opt.top().first};
		auto [l1, r1] = s1.top().first;
		auto [l2, r2] = s2.top().first;
		if (r1 >= l2) {
			ans = min(ans, pair<int, int> {r1 - l2, r2 - l1});
		}
		if (qans[i] < int(1e8)) {
			ans = min(ans, pair<int, int> {0, qans[i]});
		}
		cout << ans.second << endl;
	}
}

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