Submission #1210743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210743		salmon	Event Hopping 2 (JOI21_event2)	C++20	0 / 100	2572 ms	6040 KiB

event2

#include <bits/stdc++.h>
using namespace std;

int N;
int K;
int l[100100];
int r[100100];
vector<int> ropt;
vector<int> lopt;
int ft[200100];
int seten[100100];
vector<int> de;
vector<int> taken;

int query(int i){
	int v = 0;
	while(i != 0){
		v = max(v,ft[i]);
		i -= (i&(-i));
	}
	return v;
}

void update(int i, int k){
	while(i <= N * 2){
		ft[i] = max(ft[i],k);
		i += (i&(-i));
	}
}


int main(){
	
	scanf(" %d",&N);
	scanf(" %d",&K);

	vector<pair<int,int>> v;
	
	for(int i = 0; i < N; i++){
		scanf(" %d",&l[i]);
		scanf(" %d",&r[i]);
	
		de.push_back(l[i]);
		de.push_back(r[i]);
	}
	
	sort(de.begin(),de.end());
	de.resize(unique(de.begin(), de.end() ) - de.begin() );
	for(int i = 0; i < N; i++){
		l[i] = lower_bound(de.begin(), de.end(), l[i]) - de.begin() + 1;
		r[i] = lower_bound(de.begin(),de.end(), r[i]) - de.begin() + 1; 
		//printf("%d %d\n",l[i],r[i]);
		v.push_back({r[i],l[i]});
	}

	sort(v.begin(),v.end());
	for(int i = 1 ; i <= N * 2; i++) ft[i] = 0;
		
	int cont = 0;
	
	for(int i = 0; i < N; i++){
		if(query(v[i].second) + 1 > cont){
			cont++;
			ropt.push_back(v[i].first);
		}
		
		update(v[i].first, query(v[i].second) + 1);
	}
	
	v.clear();
	
	for(int i = 0; i < N; i++){
		v.push_back({l[i],r[i]});
	}
	sort(v.begin(),v.end());
	for(int i = 1; i <= N * 2; i++) ft[i] = 0;
	
	cont = 0;
	
	for(int i = N - 1; i >= 0; i--){
		//printf("%d\n",query(N * 2 + 1 - v[i].second));
		if(query(N * 2 + 1 - v[i].second ) + 1 > cont){
			cont++;
			lopt.push_back(v[i].first);
		}
		update(N * 2 + 1 - v[i].first, query(N * 2 + 1 - v[i].second) + 1);
	}
	
	reverse(lopt.begin(),lopt.end());
	
	for(int i = 0; i <= cont; i++){
		seten[i] = -1;
		//printf("%d %d\n",lopt[i],ropt[i]);
	}
	
	vector<int> taken;
	
	for(int i = 0; i < N; i++){
		int it = upper_bound(ropt.begin(),ropt.end(),r[i]) - ropt.begin() - 1;
		int bit = lower_bound(lopt.begin(),lopt.end(),l[i]) - lopt.begin();
		
		if(cont - (it - bit + 1) < K - 1) continue;
	
		bool die = false;
	
		for(int i  = bit; i <= it; i++){
			if(seten[i] != -1){
				die = true;
				break;
			}
		}
		
		if(die) continue;
		
		for(int j : taken){
			if(r[j] <= l[i] || r[i] <= l[j]) continue;
			else die = true;
		}
		
		if(die) continue;
		
		taken.push_back(i);
		for(int i  = bit; i <= it; i++){
			seten[i] = 0;
		}
		
		cont -= (it - bit + 1);
		K--;
	}
	
	for(int i : taken) printf("%d\n",i+1);
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
event2.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         scanf(" %d",&K);
      |         ~~~~~^~~~~~~~~~
event2.cpp:40:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |                 scanf(" %d",&l[i]);
      |                 ~~~~~^~~~~~~~~~~~~
event2.cpp:41:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |                 scanf(" %d",&r[i]);
      |                 ~~~~~^~~~~~~~~~~~~

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