oj.uz

Submission #976263

# Submission time Handle Problem Language Result Execution time Memory
976263 2024-05-06T11:16:59 Z happy_node Event Hopping 2 (JOI21_event2) C++17
1 / 100
 70 ms 46292 KB 
#include <bits/stdc++.h>
using namespace std; 

const int MX=1e5+5;
int N,K;
int L[MX], R[MX], nxt[MX], deg[MX];

vector<pair<int,int>> ptL[MX], ptR[MX];
map<int,int> id;
vector<int> adj[MX];

int up[MX][20];

void dfs(int v) {
	for(int k=1;k<20;k++) {
		up[v][k]=up[up[v][k-1]][k-1];
	}

	for(auto u:adj[v]) {
		up[u][0]=v;
		dfs(u);
	}
}

int calc(int l, int r) {
	int v=nxt[l], res=0;
	if(v==1e9) return 0;
	if(R[v]>r) return 0;

	for(int k=19;k>=0;k--) {
		if(up[v][k]!=0 && R[up[v][k]]<=r) {
			res+=1<<k;
			v=up[v][k];
		}
	}
	return res+1;
}

bool chk(pair<int,int> p, pair<int,int> q) {
	if(p.second<=q.first) return false;
	return true;
}

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

	cin>>N>>K;
	for(int i=1;i<=N;i++) {
		cin>>L[i]>>R[i];
		id[L[i]]=0;
		id[R[i]]=0;
	}
	int z=0;
	for(auto &[x,y]:id) {
		y=++z;
	}
	for(int i=1;i<=N;i++) {
		L[i]=id[L[i]];
		R[i]=id[R[i]];

		ptL[L[i]].push_back({R[i],i});
		ptR[R[i]].push_back({L[i],i});
	}

	pair<int,int> lst={1e9,1e9};

	for(int p=z;p>=1;p--) {
		for(auto [r,id]:ptL[p]) {
			lst=min(lst,make_pair(r,id));
		}
		nxt[p]=lst.second;
		for(auto [l,id]:ptR[p]) {
			if(lst.second!=1e9) {
				adj[lst.second].push_back(id);
			}
		}
	}

	for(int i=1;i<=N;i++) {
		for(auto j:adj[i]) deg[j]+=1;
	}
	
	for(int i=1;i<=N;i++) {
		if(!deg[i]) {
			dfs(i);
		}
	}

	set<pair<int,int>> ranges;

	ranges.insert({1,1});
	ranges.insert({z,z});

	vector<int> ans;

	for(int i=1;i<=N;i++) {
		auto it=ranges.lower_bound(make_pair(R[i],0));
		assert(it!=ranges.begin());
		it--;
		if(chk(*it,make_pair(L[i],R[i]))) continue; // intersected
		auto itt=ranges.lower_bound(make_pair(R[i],0));
		assert(itt!=ranges.end());

		int a=it->second,b=itt->first;
		if(1+calc(a,L[i])+calc(R[i],b)+calc(1,a)+calc(b,z)>=K) {
			assert(L[i]<=R[i]);
			ranges.insert({L[i],R[i]});
			ans.push_back(i);
		}
		if(ans.size()==K) break;
	}	

	if(ans.size()<K) {
		cout<<-1<<'\n';
		return 0;
	}

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

Compilation message

event2.cpp: In function 'int main()':
event2.cpp:110:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  110 |   if(ans.size()==K) break;
      |      ~~~~~~~~~~^~~
event2.cpp:113:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  113 |  if(ans.size()<K) {
      |     ~~~~~~~~~~^~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 3 ms 8796 KB Output is correct
4 Runtime error 70 ms 46292 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 3 ms 8800 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 3 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8852 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 2 ms 8792 KB Output is correct
10 Correct 2 ms 8792 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 2 ms 8960 KB Output is correct
13 Correct 2 ms 9008 KB Output is correct
14 Correct 2 ms 8792 KB Output is correct
15 Correct 2 ms 9008 KB Output is correct
16 Correct 3 ms 8796 KB Output is correct
17 Correct 2 ms 8796 KB Output is correct
18 Correct 2 ms 8792 KB Output is correct
19 Correct 2 ms 8796 KB Output is correct
20 Correct 2 ms 9012 KB Output is correct
21 Correct 2 ms 8792 KB Output is correct
22 Correct 2 ms 8796 KB Output is correct
23 Correct 2 ms 8796 KB Output is correct
24 Correct 2 ms 8796 KB Output is correct
25 Correct 2 ms 8792 KB Output is correct
26 Correct 2 ms 8796 KB Output is correct
27 Correct 2 ms 8796 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 3 ms 8800 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 3 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8852 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 2 ms 8792 KB Output is correct
10 Correct 2 ms 8792 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 2 ms 8960 KB Output is correct
13 Correct 2 ms 9008 KB Output is correct
14 Correct 2 ms 8792 KB Output is correct
15 Correct 2 ms 9008 KB Output is correct
16 Correct 3 ms 8796 KB Output is correct
17 Correct 2 ms 8796 KB Output is correct
18 Correct 2 ms 8792 KB Output is correct
19 Correct 2 ms 8796 KB Output is correct
20 Correct 2 ms 9012 KB Output is correct
21 Correct 2 ms 8792 KB Output is correct
22 Correct 2 ms 8796 KB Output is correct
23 Correct 2 ms 8796 KB Output is correct
24 Correct 2 ms 8796 KB Output is correct
25 Correct 2 ms 8792 KB Output is correct
26 Correct 2 ms 8796 KB Output is correct
27 Correct 2 ms 8796 KB Output is correct
28 Correct 5 ms 11612 KB Output is correct
29 Incorrect 5 ms 11852 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 3 ms 8796 KB Output is correct
4 Runtime error 70 ms 46292 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -