Submission #443576

#	Time	Username	Problem	Language	Result	Execution time	Memory
443576		dutch	Event Hopping 2 (JOI21_event2)	C++17	0 / 100	187 ms	27040 KiB

event2

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int INF = 1e16, LIM = 1e5+1, LOG = 18;

template<class T> struct SegmentTree{
	int n = 1, i; vector<T> a; T ID;
	function<T(T, T)> comb = [](T x, T y){ return min(x, y); };
	SegmentTree(int N, T id) : ID(id) { while((n+=n)<N); a.assign(2*n, ID); }
	SegmentTree& operator[](int j){ i=j+n; return *this; }
	void operator=(T v){
		for(a[i]=v; i/=2; ) a[i] = comb(a[2*i], a[2*i+1]); }
	T operator()(int l, int r){
		T x = ID;
		for(l+=n, r+=n+1; l<r; l/=2, r/=2){
			if(l & 1) x = comb(x, a[l++]);
			if(r & 1) x = comb(x, a[--r]);
		}
		return x;
	}
	int find(int x, int l, int r){
		if(r <= i || a[x] < a[0]) return n;
		if(r - l < 2) return l;
		int m = (l + r) / 2, y = find(2*x, l, m);
		return y < n ? y : find(2*x+1, m, r);
	}
	int find(int l, T v){ // first value >= v with index >= l
		i = l; a[0] = v;
		return find(1, 0, n);
	}
};

int n, k, l[LIM], r[LIM], byR[LIM], p[LIM], g[LOG][LIM], rS[LIM];
bool removed[LIM];
set<array<int, 2>> s, selected;
const array<int, 2> ID = {INF, INF};

int best(int u, int v){
	int res = 0;
	for(int i=LOG; --i>=0; )
		if(g[i][u] < v) res |= (1<<i), u = g[i][u];
	return res + 1;
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> k;
	SegmentTree<int> maxL(n, -INF);
	SegmentTree<array<int, 2>> minL(n, ID);
	maxL.comb = [](int x, int y){ return max(x, y); };

	for(int i=0; i<n; ++i) cin >> l[i] >> r[i];

	iota(byR, byR+n, 0LL);
	sort(byR, byR+n, [](int &x, int &y){ return r[x] < r[y]; });

	for(int i=0; i<n; ++i){
		maxL[i] = l[byR[i]];
		minL[i] = {l[byR[i]], byR[i]};
		p[byR[i]] = i;
		rS[i] = r[byR[i]];
	}
	g[0][n] = n;

	for(int j=0; j<LOG; ++j)
		for(int i=0; i<=n; ++i)
			g[j][i] = j ? g[j-1][g[j-1][i]] : min(n, maxL.find(i+1, r[byR[i]]));
	
	int curr = best(0, n);
	if(curr < k){
		cout << -1;
		return 0;
	}

	s.insert({0, n});

	auto remove = [&](int i){
		if(!removed[i]){
			removed[i] = 1;
			auto f = --s.lower_bound({p[i]+1, 0});
			int a = (*f)[0], b = (*f)[1];
			curr += (best(a, p[i]) + best(p[i]+1, b) - best(a, b));
			s.erase(f);
			if(p[i]+1<b) s.insert({p[i]+1, b});
			if(a < p[i]) s.insert({a, p[i]});
		}
	};

	for(int i=0, z=k; i<n && z; ++i){
		if(removed[i]) continue;

		auto f = --s.lower_bound({p[i], 0});
		int a = (*f)[0], b = (*f)[1];
		int v = (best(a, p[i]) + best(p[i]+1, b) - best(a, b));
		if(1 + v + curr < z) continue;

		--z;
		int y = lower_bound(rS, rS+n, l[i]+1) - rS;
		array<int, 2> j;
		while((j = minL(y, p[i])) != ID){
			remove(j[1]);
			minL[p[j[1]]] = ID;
		}
		while((j = minL(p[i], n-1))[0] < r[i]){
			remove(j[1]);
			minL[p[j[1]]] = ID;
		}
		cout << i+1 << '\n';
	}
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 1
• Subtask 3: 0 / 31
• Subtask 4: 0 / 61