oj.uz

Submission #975658

# Submission time Handle Problem Language Result Execution time Memory
975658 2024-05-05T16:34:25 Z happy_node Event Hopping 2 (JOI21_event2) C++17
0 / 100
 3000 ms 30588 KB 
#include <bits/stdc++.h>
using namespace std; 

const int MX=4e5+5, inf=1e9;

int N,K;
vector<pair<int,int>> vv;
vector<array<int,3>> v;

int dp[MX];
map<int,int> id;

int val[MX];
vector<pair<int,int>> op[MX];

bool vis[MX];

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin>>N>>K;

	for(int i=1;i<=N;i++) {
		int l,r;
		cin>>l>>r;
		v.push_back({r,l,i});
		vv.push_back({l,r});
		id[l]=0;
		id[r]=0;
	}

	int z=1;
	for(auto &[x,y]:id) y=z++;

	for(auto &[r,l,i]:v) {
		r=id[r];
		l=id[l];
	}
	for(auto &[l,r]:vv) {
		l=id[l];
		r=id[r];
	}

	for(auto [r,l,i]:v) {
		op[l].push_back({r,i});
	}

	for(int i=2*N;i>=1;i--) {
		for(auto [j,ii]:op[i]) {
			dp[i]=max(dp[i],dp[j]+1);
		}
		dp[i]=max(dp[i],dp[i+1]);
	}

	val[0]=1e9;
	for(int i=2*N;i>=1;i--) {
		if(val[dp[i]]==0) {
			val[dp[i]]=i;
		}
	}

	vector<int> ans;

	set<int> pts;

	while(K>0) {
		int p=-1;
		for(int i=0;i<N;i++) {
			auto [r,l,ii]=v[i];
			if(vis[i]) continue;
			if(r>val[K-1]) continue;
			auto it=pts.lower_bound(l);
			if(it==pts.end() || *it>=r) {
				if(p==-1 || ii<v[p][2]) p=i;
			}
		}
		if(p==-1) {
			cout<<-1<<endl;
			return 0;
		}
		
		ans.push_back(v[p][2]);
		vis[p]=true;
		for(int k=v[p][1];k<v[p][0];k++) pts.insert(k);
		K--;
	}

	sort(ans.begin(),ans.end());

	for(auto x:ans) {
		cout<<x<<'\n';
	}

}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Execution timed out 3083 ms 30588 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 3 ms 12632 KB Output is correct
3 Correct 3 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12632 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 3 ms 12636 KB Output is correct
8 Incorrect 3 ms 12636 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 3 ms 12632 KB Output is correct
3 Correct 3 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12632 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 3 ms 12636 KB Output is correct
8 Incorrect 3 ms 12636 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Execution timed out 3083 ms 30588 KB Time limit exceeded
5 Halted 0 ms 0 KB -