Submission #447943

#	Time	Username	Problem	Language	Result	Execution time	Memory
447943		keta_tsimakuridze	Event Hopping 2 (JOI21_event2)	C++14	8 / 100	350 ms	56388 KiB

event2

#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
const int N=2e5+5,mod=1e9+7,LG = 22,inf = mod;
int t,n,k,l[N],r[N],mn[N],mx[N],parR[N][LG],parL[N][LG],Lg,suf[N],pref[N],h1[N],h[N],fix[N],f[N];
vector<int> Ans;
set<pair<int,int> > L,R;
pair<pair<int,int>,int> p[N];
 main(){
	cin>>n>>k;
	Lg = log2(n) + 1;
	for(int i=1;i<=n;i++){
		cin>>p[i].f.f>>p[i].f.s;
		l[i] = p[i].f.f;
		r[i] = p[i].f.s;
		p[i].s = i;
	}
	sort(p+1,p+n+1);
	p[n+1].f.s = 1e9 + 5;
	mn[n+1] = n+1;
	for(int i=n;i>=1;i--) {
		mn[i] = mn[i+1];
		if(p[i].f.s < p[mn[i]].f.s) mn[i] = i;
		int l = i+1, r = n,id = -1;
		while(l<=r) {
			int mid = (l+r)/2;
			if(p[mid].f.f >= p[i].f.s) {
				id = mid;
				r = mid - 1;
			}
			else l = mid + 1;
		}
		if(id > 0) {
			parR[p[i].s][0] =  p[mn[id]].s;
			h1[p[i].s] = h1[p[mn[id]].s] + 1;
			for(int j=1; j<=Lg; j++) parR[p[i].s][j] = parR[parR[p[i].s][j-1]][j-1];
		}
	}
	for(int i=1;i<=n;i++) {
		swap(p[i].f.f,p[i].f.s);
	}
	sort(p+1,p+n+1);
	p[0].f.s = 0;
	mx[0] = 0;
	for(int i=1;i<=n;i++) {
		mx[i] = mx[i-1];
		if(p[i].f.s > p[mx[i]].f.s) mx[i] = i;		
		int l = 1, r = i-1, id = -1;
		while(l<=r) {
			int mid = (l+r)/2;
			if(p[mid].f.f <= p[i].f.s) {
				id = mid;
				l = mid + 1;
			}
			else r = mid - 1;
		}		
		if(id > 0) {
			parL[p[i].s][0] = p[mx[id]].s;
			h[p[i].s] = h[p[mx[id]].s] + 1;
			
			for(int j=1; j<=Lg; j++) parL[p[i].s][j] = parL[parL[p[i].s][j-1]][j-1];
		}		
	}
	L.insert({-inf,0});
	R.insert({inf,0});
	R.insert({-inf,0});
	L.insert({inf,0});
	l[0] = inf;
	r[0] = 0;
	for(int i=1;i<=n;i++){
		int up = (*L.upper_bound({r[i],0})).f;
		int d = (*--R.upper_bound({l[i]+1,0})).f;
	
		if(r[(*--L.upper_bound({l[i]+1,0})).s] > l[i]) continue;
		
		if(l[(*R.upper_bound({r[i],0})).s] < r[i]) continue;
		if((*R.upper_bound({l[i] + 1,0})).f < r[i]) continue;
		int u = i;
		int ss =  suf[(*L.upper_bound({r[i],0})).s], pr =  pref[(*--R.upper_bound({l[i]+1,0})).s],ans = 0;
		for(int j=Lg; j>=0; j--) {
			if(parR[u][j] && r[parR[u][j]] <= up) {
				ans += 1<<j;
				u = parR[u][j];
			}
		}
		int ans1 = ans;
		u = i;
		for(int j=Lg; j>=0; j--) {
			if(parL[u][j] && l[parL[u][j]] >= d) {
				ans += 1<<j;
				u = parL[u][j];
			}
		}
		if(ans + pr + ss + 1>=k) {
			pref[i] = pr + ans - ans1 + 1;
			suf[i] = ss + ans1 + 1;
			L.insert({l[i],i});
			R.insert({r[i],i});
			Ans.push_back(i);
			if(Ans.size()==k) break;
		}
	}

	if(!Ans.size()) cout<<-1;
	else {	
		
		int x = 0;
		//if(Ans.size()!=k) cout<<n/x;
		for(int i=0;i<Ans.size();i++) cout<<Ans[i]<<" ";
	}
	
}

Compilation message (stderr)

event2.cpp:11:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   11 |  main(){
      |  ^~~~
event2.cpp: In function 'int main()':
event2.cpp:102:17: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  102 |    if(Ans.size()==k) break;
      |       ~~~~~~~~~~^~~
event2.cpp:111:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |   for(int i=0;i<Ans.size();i++) cout<<Ans[i]<<" ";
      |               ~^~~~~~~~~~~
event2.cpp:109:7: warning: unused variable 'x' [-Wunused-variable]
  109 |   int x = 0;
      |       ^

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