Submission #1278093

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278093		namhh	Event Hopping 2 (JOI21_event2)	C++20	100 / 100	375 ms	30364 KiB

event2

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 2e5+5;
const int lg = 18;
int n,k,st[N][lg],nxt[N];
pii a[N];
map<int,int>mp;
multiset<pii>s;
void build(){
	for(int i = 1; i <= mp.size(); i++){
	    st[i][0] = nxt[i];
	    if(nxt[i] == 1e9) st[i][0] = 0;
	}
	for(int j = 1; j < lg; j++){
		for(int i = 1; i <= mp.size(); i++) st[i][j] = st[st[i][j-1]][j-1];
	}
}
int jump(int u, int v){
	int sum = 0;
	for(int i = lg-1; i >= 0; i--){
		if(st[u][i] > u && st[u][i] <= v){
			sum += (1 << i);
			u = st[u][i];
		}
	}
	return sum;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> k;
	for(int i = 1; i <= n; i++){
		cin >> a[i].fi >> a[i].se;
		mp[a[i].fi]++;
		mp[a[i].se]++;
	}
	int cnt = 0;
	for(auto it: mp) mp[it.fi] = ++cnt;
	for(int i = 1; i <= n; i++){
		a[i].fi = mp[a[i].fi];
		a[i].se = mp[a[i].se];
	}
	for(int i = 1; i <= mp.size(); i++) nxt[i] = 1e9;
	for(int i = 1; i <= n; i++) nxt[a[i].fi] = min(nxt[a[i].fi],a[i].se);
	for(int i = mp.size()-1; i >= 1; i--) nxt[i] = min(nxt[i],nxt[i+1]);
	build();
	s.insert({1,1});
	s.insert({mp.size(),mp.size()});
	int cur = jump(1,mp.size());
	if(cur < k){
		cout << -1;
		return 0;
	}
    for(int i = 1; i <= n; i++){
    	auto[x,y] = a[i];
    	auto reze = s.lower_bound({y,-1});
    	auto[x1,x2] = *reze;
    	--reze;
    	auto[y2,y1] = *reze;
    	if(x < y1) continue;
    	int nw = cur+1-jump(y1,x1)+jump(y1,x)+jump(y,x1);
    	if(nw >= k){
    		cur = nw;
    		cout << i << "\n";
    		s.insert({x,y});
		}
		if(s.size() == k+2) return 0;
	}
}

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