제출 #447964

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
447964		keta_tsimakuridze	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	534 ms	57656 KiB

event2

#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,pair<int,int> > 
using namespace std;
const int N=2e5+5,mod=1e10+7,LG = 22,inf = mod;
int t,n,k,l[N],r[N],mn[N],mx[N],parR[N][LG],parL[N][LG],Lg,h1[N],h[N],fix[N],f[N];
vector<int> Ans;
set<pair<int,int> > R;
set<pii >L;
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,0}});
	R.insert({inf,0});
	R.insert({-inf,0});
	L.insert({inf,{0,0}});
	l[0] = inf;
	r[0] = 0;
	int all = 0;
	for(int i=1;i<=n;i++){
		int up = (*L.upper_bound({r[i],{0,0}})).f;
		int d = (*--R.upper_bound({l[i]+1,0})).f;
		if(r[(*--L.upper_bound({l[i]+1,{0,0}})).s.f] > 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 =  (*L.upper_bound({r[i]-1,{0,0}})).s.s;
		int 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(all - ss + ans + 1>=k) {

			all = all - ss + ans + 1;
			pii p = (*L.upper_bound({r[i]-1,{0,0}}));
			L.erase(p);
			L.insert({p.f,{p.s.f,ans1}});
			L.insert({l[i],{i,ans-ans1}});
			R.insert({r[i],i});
		
			Ans.push_back(i);
			if(Ans.size()==k) break;
		}
	}
	if(!Ans.size()) cout<<-1;
	else {	
		int x = 0;
		for(int i=0;i<Ans.size();i++) cout<<Ans[i]<<" ";
	}
	
}

컴파일 시 표준 에러 (stderr) 메시지

event2.cpp:13:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   13 |  main(){
      |  ^~~~
event2.cpp: In function 'int main()':
event2.cpp:112: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]
  112 |    if(Ans.size()==k) break;
      |       ~~~~~~~~~~^~~
event2.cpp:118: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]
  118 |   for(int i=0;i<Ans.size();i++) cout<<Ans[i]<<" ";
      |               ~^~~~~~~~~~~
event2.cpp:117:7: warning: unused variable 'x' [-Wunused-variable]
  117 |   int x = 0;
      |       ^

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