oj.uz

Submission #976264

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

const int MX=2e5+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 3 ms 16732 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Correct 4 ms 16732 KB Output is correct
4 Correct 130 ms 53964 KB Output is correct
5 Correct 125 ms 55676 KB Output is correct
6 Correct 123 ms 55240 KB Output is correct
7 Correct 119 ms 54832 KB Output is correct
8 Correct 130 ms 55876 KB Output is correct
9 Correct 131 ms 55692 KB Output is correct
10 Correct 127 ms 55240 KB Output is correct
11 Correct 120 ms 54728 KB Output is correct
12 Correct 116 ms 51180 KB Output is correct
13 Correct 110 ms 50936 KB Output is correct
14 Correct 106 ms 50916 KB Output is correct
15 Correct 104 ms 50636 KB Output is correct
16 Correct 92 ms 45824 KB Output is correct
17 Correct 92 ms 45928 KB Output is correct
18 Correct 90 ms 45748 KB Output is correct
19 Correct 94 ms 44372 KB Output is correct
20 Incorrect 96 ms 44372 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16728 KB Output is correct
2 Correct 4 ms 16732 KB Output is correct
3 Correct 3 ms 16732 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Correct 3 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 4 ms 16732 KB Output is correct
8 Correct 3 ms 16732 KB Output is correct
9 Correct 4 ms 16732 KB Output is correct
10 Correct 3 ms 16832 KB Output is correct
11 Correct 4 ms 16732 KB Output is correct
12 Correct 3 ms 16740 KB Output is correct
13 Correct 4 ms 16888 KB Output is correct
14 Correct 3 ms 16728 KB Output is correct
15 Correct 4 ms 16732 KB Output is correct
16 Correct 4 ms 16732 KB Output is correct
17 Correct 3 ms 16732 KB Output is correct
18 Correct 3 ms 16732 KB Output is correct
19 Correct 4 ms 16756 KB Output is correct
20 Correct 4 ms 16732 KB Output is correct
21 Correct 3 ms 16732 KB Output is correct
22 Correct 4 ms 16848 KB Output is correct
23 Correct 4 ms 16836 KB Output is correct
24 Correct 3 ms 16732 KB Output is correct
25 Correct 4 ms 16732 KB Output is correct
26 Correct 4 ms 16732 KB Output is correct
27 Correct 4 ms 16732 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16728 KB Output is correct
2 Correct 4 ms 16732 KB Output is correct
3 Correct 3 ms 16732 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Correct 3 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 4 ms 16732 KB Output is correct
8 Correct 3 ms 16732 KB Output is correct
9 Correct 4 ms 16732 KB Output is correct
10 Correct 3 ms 16832 KB Output is correct
11 Correct 4 ms 16732 KB Output is correct
12 Correct 3 ms 16740 KB Output is correct
13 Correct 4 ms 16888 KB Output is correct
14 Correct 3 ms 16728 KB Output is correct
15 Correct 4 ms 16732 KB Output is correct
16 Correct 4 ms 16732 KB Output is correct
17 Correct 3 ms 16732 KB Output is correct
18 Correct 3 ms 16732 KB Output is correct
19 Correct 4 ms 16756 KB Output is correct
20 Correct 4 ms 16732 KB Output is correct
21 Correct 3 ms 16732 KB Output is correct
22 Correct 4 ms 16848 KB Output is correct
23 Correct 4 ms 16836 KB Output is correct
24 Correct 3 ms 16732 KB Output is correct
25 Correct 4 ms 16732 KB Output is correct
26 Correct 4 ms 16732 KB Output is correct
27 Correct 4 ms 16732 KB Output is correct
28 Correct 7 ms 19544 KB Output is correct
29 Incorrect 7 ms 19548 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Correct 4 ms 16732 KB Output is correct
4 Correct 130 ms 53964 KB Output is correct
5 Correct 125 ms 55676 KB Output is correct
6 Correct 123 ms 55240 KB Output is correct
7 Correct 119 ms 54832 KB Output is correct
8 Correct 130 ms 55876 KB Output is correct
9 Correct 131 ms 55692 KB Output is correct
10 Correct 127 ms 55240 KB Output is correct
11 Correct 120 ms 54728 KB Output is correct
12 Correct 116 ms 51180 KB Output is correct
13 Correct 110 ms 50936 KB Output is correct
14 Correct 106 ms 50916 KB Output is correct
15 Correct 104 ms 50636 KB Output is correct
16 Correct 92 ms 45824 KB Output is correct
17 Correct 92 ms 45928 KB Output is correct
18 Correct 90 ms 45748 KB Output is correct
19 Correct 94 ms 44372 KB Output is correct
20 Incorrect 96 ms 44372 KB Output isn't correct
21 Halted 0 ms 0 KB -