oj.uz

Submission #947061

# Submission time Handle Problem Language Result Execution time Memory
947061 2024-03-15T12:53:34 Z vjudge1 Event Hopping 2 (JOI21_event2) C++17
0 / 100
 3000 ms 60620 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10,lg=20;
vector<long long>res;
long long n,k,sp[lg][maxn],dp[maxn],lnk[maxn],last[maxn];
pair<long long,long long>all[maxn];
vector<long long>alll[maxn],allr[maxn];
long long ted=0;
vector<pair<long long,long long>>allv;
set<pair<long long,long long>>inds;

long long callen(long long ind){
  if(ind>=(int)allv.size()){
      return 0;
  }
	long long l=allv[ind].first;
	auto x=inds.lower_bound(make_pair(l,l));
	long long bad=(*x).first;
	x--;
	long long ghabl=(*x).second;
	if(l<=ghabl){
		return 0;
	}
	long long ret=0;
	while(lnk[l]<bad&&l<bad){
		//cout<<l<<endl;
		ret++;
		l=last[lnk[l]];
	}
	//cout<<allv[ind].first<<" "<<ret<<" injy:"<<endl;
	//for(auto x:inds){
	  //cout<<x.first<<" "<<x.second<<endl;
	//}
	return ret;
}

void vorod(){
	cin>>n>>k;
	vector<long long>allind;
	for(long long i=1;i<=n;i++){
		cin>>all[i].first>>all[i].second;
//		all[i].second--;
		allind.push_back(all[i].first);
		allind.push_back(all[i].second);
	}
	sort(allind.begin(),allind.end());
	allind.resize(unique(allind.begin(),allind.end())-allind.begin());
	for(long long i=1;i<=n;i++){
		all[i].first=lower_bound(allind.begin(),allind.end(),all[i].first)-allind.begin();
		all[i].second=lower_bound(allind.begin(),allind.end(),all[i].second)-allind.begin();
		alll[all[i].first].push_back(i);
		allr[all[i].second].push_back(i);
		////cout<<i<<" "<<all[i].first<<" "<<all[i].second<<endl;
	}
}
void pre(){
	inds.insert(make_pair(-1,-1));
	inds.insert(make_pair(maxn,maxn));
	set<pair<long long,long long>>st;
	for(long long i=0;i<maxn;i++){
		last[i]=maxn+2;
	}
	for(long long i=0;i<maxn;i++){
		long long mn=maxn+2;
		for(auto x:alll[i]){
			mn=min(mn,all[x].second);
		}
		while((long long)st.size()>0&&(*st.rbegin()).first>=mn){
			st.erase(*st.rbegin());
		}
		for(auto x:alll[i]){
			if(all[x].second==mn){
				st.insert(make_pair(all[x].second,x));
				mn=-1;
			}
		}
		for(auto x:allr[i]){
			if(st.count(make_pair(i,x))==1){
				st.erase(make_pair(i,x));
				allv.push_back(make_pair(all[x].first,all[x].second));
				last[all[x].first-1]=all[x].first;
				lnk[all[x].first]=all[x].second;
			}
		}
	}
	for(long long i=maxn-2;i>=0;i--){
		last[i]=min(last[i],last[i+1]);
	}
	for(long long i=0;i<maxn;i++){
		for(long long j=0;j<lg;j++){
			sp[j][i]=maxn+2;
		}
	}
	for(long long i=1;i<=n;i++){
		sp[0][all[i].first]=min(sp[0][all[i].first],last[all[i].second]);
	}
	for(long long i=1;i<lg;i++){
		for(long long j=0;j<maxn;j++){
			sp[i][j]=sp[i-1][sp[i-1][j]];
		}
	}
	dp[0]=callen(0);
	ted+=dp[0];
}

bool eshy(long long l,long long r,long long ll,long long rr){
	if(l>ll){
		swap(l,ll);
		swap(r,rr);
	}
	return ll<=r;
}

bool esh(long long a,long long b){
	return eshy(all[a].first,all[a].second,all[b].first,all[b].second);
}

/*long long cal(){
	long long ret=0,r=-1;
	for(auto x:allv){
		long long f=1;
		auto z=inds.lower_bound(make_pair(x.first,x.first));
		if((long long)inds.size()>0&&(*inds.rbegin()).first>=x.first){
			if(eshy(x.first,x.second,(*z).first,(*z).second)){
				f=0;
			}
		}
		if((long long)inds.size()>0&&(*inds.begin()).first<x.first){
			z--;
			if(eshy(x.first,x.second,(*z).first,(*z).second)){
				f=0;
			}
		}
		if(x.first<=r||f==0){
			continue;
		}
		ret++;
		r=x.second;
	}
	return ret;
}*/

void ins(long long i){
  res.push_back(i);
	auto x=inds.lower_bound(make_pair(all[i].first,all[i].second));
	auto bad=*x;
	x--;
	auto ghabl=*x;
	long long p1=lower_bound(allv.begin(),allv.end(),make_pair(ghabl.second+1,-1ll))-allv.begin();
	long long p2=lower_bound(allv.begin(),allv.end(),make_pair(all[i].second+1,-1ll))-allv.begin();
	long long p3=lower_bound(allv.begin(),allv.end(),make_pair(bad.second+1,-1ll))-allv.begin();
	inds.insert(make_pair(all[i].first,all[i].second));
	if(p1!=p3){
		ted-=dp[p1];
	}
	dp[p1]=callen(p1);
	dp[p2]=callen(p2);
	if(p1!=p2){
		ted+=dp[p1];
	}
	if(p2!=p3){
		ted+=dp[p2];
	}
	//cout<<"insy: "<<i<<" "<<ted<<endl;
}

void erase(long long i){
  res.pop_back();
	inds.erase(make_pair(all[i].first,all[i].second));
	auto x=inds.lower_bound(make_pair(all[i].first,all[i].second));
	auto bad=*x;
	x--;
	auto ghabl=*x;
	long long p1=lower_bound(allv.begin(),allv.end(),make_pair(ghabl.second+1,-1ll))-allv.begin();
	long long p2=lower_bound(allv.begin(),allv.end(),make_pair(all[i].second+1,-1ll))-allv.begin();
	long long p3=lower_bound(allv.begin(),allv.end(),make_pair(bad.second+1,-1ll))-allv.begin();
	if(p1!=p2){
		ted-=dp[p1];
	}
	if(p2!=p3){
		ted-=dp[p2];
	}
	dp[p1]=callen(p1);
	dp[p2]=callen(p2);
	if(p1!=p3){
		ted+=dp[p1];
	}
}

void can(long long i){
	auto x=all[i];
	auto z=inds.lower_bound(make_pair(x.first,x.first));
	if((long long)inds.size()>0&&(*inds.rbegin()).first>=x.first){
		if(eshy(x.first,x.second,(*z).first,(*z).second)){
			return ;
		}
	}
	if((long long)inds.size()>0&&(*inds.begin()).first<x.first){
		z--;
		if(eshy(x.first,x.second,(*z).first,(*z).second)){
			return ;
		}
	}
	ins(i);
	if(ted+(long long)res.size()<k){
		erase(i);
	}
}

void solve(){
	for(long long i=1;i<=n;i++){
		if((long long)res.size()==k){
			break;
		}
		can(i);
	}
}

void khor(){
	if((long long)res.size()<k){
		cout<<-1<<"\n";
		return ;
	}
	for(auto x:res){
		cout<<x<<"\n";
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	////cout.tie(0);
	//freopen("inp.txt","r",stdin);
	vorod();
	pre();
//	//cout<<"salam"<<endl;
//	return 0;
	solve();
	khor();
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 44888 KB Output is correct
2 Correct 13 ms 44888 KB Output is correct
3 Correct 14 ms 44888 KB Output is correct
4 Execution timed out 3040 ms 60620 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 45068 KB Output is correct
2 Correct 13 ms 44792 KB Output is correct
3 Correct 13 ms 44892 KB Output is correct
4 Correct 12 ms 44740 KB Output is correct
5 Correct 13 ms 44688 KB Output is correct
6 Correct 13 ms 44892 KB Output is correct
7 Correct 13 ms 44896 KB Output is correct
8 Correct 12 ms 44784 KB Output is correct
9 Correct 13 ms 44888 KB Output is correct
10 Correct 12 ms 44892 KB Output is correct
11 Correct 13 ms 44744 KB Output is correct
12 Correct 13 ms 44892 KB Output is correct
13 Correct 13 ms 44852 KB Output is correct
14 Correct 13 ms 44892 KB Output is correct
15 Correct 13 ms 44892 KB Output is correct
16 Incorrect 13 ms 44704 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 45068 KB Output is correct
2 Correct 13 ms 44792 KB Output is correct
3 Correct 13 ms 44892 KB Output is correct
4 Correct 12 ms 44740 KB Output is correct
5 Correct 13 ms 44688 KB Output is correct
6 Correct 13 ms 44892 KB Output is correct
7 Correct 13 ms 44896 KB Output is correct
8 Correct 12 ms 44784 KB Output is correct
9 Correct 13 ms 44888 KB Output is correct
10 Correct 12 ms 44892 KB Output is correct
11 Correct 13 ms 44744 KB Output is correct
12 Correct 13 ms 44892 KB Output is correct
13 Correct 13 ms 44852 KB Output is correct
14 Correct 13 ms 44892 KB Output is correct
15 Correct 13 ms 44892 KB Output is correct
16 Incorrect 13 ms 44704 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 44888 KB Output is correct
2 Correct 13 ms 44888 KB Output is correct
3 Correct 14 ms 44888 KB Output is correct
4 Execution timed out 3040 ms 60620 KB Time limit exceeded
5 Halted 0 ms 0 KB -