Submission #885560

#	Time	Username	Problem	Language	Result	Execution time	Memory
885560		willychan	Event Hopping 2 (JOI21_event2)	C++17	0 / 100	46 ms	6752 KiB

event2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds
const int N = 1e5+5;
int dp[N];
struct seg{
	int l;
	int r;
	int ind;
};

struct ST{
	vector<pair<int,int> > arr;
	int n;
	void init(int _s){
		n = _s;	
		arr.resize(4*n,{1e9,-1});
	}
	void modify(int ind,int L,int R,int x,int v){
		if(R==L){
			arr[ind] = {v,x};
			return;
		}
		int M = (R+L)/2;
		if(x<=M) modify(2*ind,L,M,x,v);
		else modify(2*ind+1,M+1,R,x,v);
		arr[ind] = min(arr[2*ind],arr[2*ind+1]);
	}
	pair<int,int> query(int ind,int L,int R,int l,int r){
		if(L==l && R==r){
			return arr[ind];
		}
		int M =(L+R)/2;
		if(r<=M) return query(2*ind,L,M,l,r);
		else if(l>M) return query(2*ind+1,M+1,R,l,r);
		else{
			return min(query(2*ind,L,M,l,M),query(2*ind+1,M+1,R,M+1,r));
		}
	}
} segtree;

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,K;cin>>n>>K;
	vector<seg> arr(n);
	segtree.init(n);
	for(int i=0;i<n;i++){
		cin>>arr[i].l>>arr[i].r;
		arr[i].ind = i+1;
	}
	stable_sort(arr.begin(),arr.end(),[](const seg &a,const seg &b){return(a.l<b.l);});
	vector<int> maxn(n+1);
	maxn[n] = 0;
	for(int i=n-1;i>=0;i--){
		int l = i;
		int r = n;
		while(r-l>1){
			int mid = (l+r)/2;
			if(arr[mid].l>=arr[i].r) r = mid;
			else l = mid;
		}
		dp[i] = maxn[r]+1;
		maxn[i] = max(maxn[i+1],dp[i]);
	}
	//for(int i=0;i<n;i++) cout<<
	vector<int> ord;
	for(int i=0;i<n;i++) ord.push_back(i);
	sort(ord.begin(),ord.end(),[&](const int &a,const int &b){return dp[a]>dp[b];});
	int head = 0;
	int b = 0;
	for(int k=K;k>=1;k--){
		while(head<n && dp[ord[head]]>=k){
			segtree.modify(1,0,n-1,ord[head],arr[ord[head]].ind);
			head++;
		}
		pair<int,int> cur = segtree.query(1,0,n-1,b,n-1);
		cout<<cur.first<<"\n";
		b = cur.second+1;
	}

	return 0;
}

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