oj.uz

Submission #975548

# Submission time Handle Problem Language Result Execution time Memory
975548 2024-05-05T13:16:56 Z happy_node Event Hopping 2 (JOI21_event2) C++17
7 / 100
 215 ms 41244 KB 
#include <bits/stdc++.h>
using namespace std; 

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

int N,K;
vector<pair<int,int>> vv;
vector<array<int,3>> v;
int dp[MX];
map<int,int> id;

set<pair<int,int>> st[MX];

struct segtree {
    	pair<int,int> t[4 * MX];
 
     	void update(int v, int l, int r, int pos, pair<int,int> val) {
           	if(l > pos || r < pos) return;
           	if(l == r) {
                 	t[v] = val;
                 	return;
           	}
           	int mid = (l + r) >> 1;
           	update(v * 2 + 0, l, mid + 0, pos, val);
           	update(v * 2 + 1, mid + 1, r, pos, val);
           	t[v] = min(t[v * 2 + 0], t[v * 2 + 1]);
     	}
 
     	pair<int,int>  query(int v, int l, int r, int ql, int qr) {
           	if(ql > r || qr < l) return make_pair(1e9,1e9);
           	if(ql <= l && qr >= r) return t[v];
           	int mid = (l + r) >> 1;
           	return min(query(v * 2 + 0, l, mid + 0, ql, qr), query(v * 2 + 1, mid + 1, r, ql, qr));
      	}
} tt;

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++;

	sort(v.begin(),v.end());
	for(auto [r,l,i]:v) {
		st[id[r]].insert({i,r});
	}

	for(int i=1;i<=2*N;i++) {
		if(st[i].size()) 
			tt.update(1,1,2*N,i,*st[i].begin());
		else
			tt.update(1,1,2*N,i,make_pair(inf,inf));
	}

	sort(vv.rbegin(),vv.rend());

	dp[0]=inf;
	for(auto [a,b]:vv) {
		int l=0,r=N,res=0;
		while(l<=r) {
			int mid=(l+r)/2;
			if(b<=dp[mid]) {
				res=mid,l=mid+1;
			} else {
				r=mid-1;
			}
		}
		dp[res+1]=max(dp[res+1],a);
	}

	if(!dp[K]) {
		cout<<-1<<'\n';
		return 0;
	}

	int cur=0, pt=0;

	set<array<int,3>> dels;
	for(auto [r,l,i]:v) {
		dels.insert({l,r,i});
	}

	id[1e9]=2*N;
	
	vector<int> ans;

	while(K>0) {
		// get min value lexicographically
		auto [V,R]=tt.query(1,1,2*N,id[cur],id[dp[K-1]]);

		ans.push_back(V);

		while(dels.size() && (*dels.begin())[0]<R) {
			auto [curL, curR, i]=*dels.begin();
			dels.erase(dels.begin());
			st[id[curR]].erase(make_pair(i,curR));

			tt.update(1,1,2*N,id[curR],(st[id[curR]].empty() 
				? make_pair(inf,inf) : *st[id[curR]].begin()));
			pt++;
		}
		cur=R;
		K--;
	}

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

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

}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11608 KB Output is correct
2 Correct 2 ms 11612 KB Output is correct
3 Correct 3 ms 11612 KB Output is correct
4 Correct 170 ms 41244 KB Output is correct
5 Correct 179 ms 41072 KB Output is correct
6 Correct 169 ms 41084 KB Output is correct
7 Correct 174 ms 41084 KB Output is correct
8 Correct 178 ms 41160 KB Output is correct
9 Correct 184 ms 41232 KB Output is correct
10 Correct 171 ms 41084 KB Output is correct
11 Correct 167 ms 41012 KB Output is correct
12 Correct 152 ms 40848 KB Output is correct
13 Correct 152 ms 40824 KB Output is correct
14 Correct 153 ms 40800 KB Output is correct
15 Correct 155 ms 40644 KB Output is correct
16 Correct 150 ms 40408 KB Output is correct
17 Correct 150 ms 40336 KB Output is correct
18 Correct 149 ms 40380 KB Output is correct
19 Correct 150 ms 40284 KB Output is correct
20 Correct 153 ms 40312 KB Output is correct
21 Correct 148 ms 40312 KB Output is correct
22 Correct 197 ms 40308 KB Output is correct
23 Correct 169 ms 40204 KB Output is correct
24 Correct 168 ms 40308 KB Output is correct
25 Correct 196 ms 40256 KB Output is correct
26 Correct 196 ms 40120 KB Output is correct
27 Correct 215 ms 40312 KB Output is correct
28 Correct 87 ms 34308 KB Output is correct
29 Correct 83 ms 34172 KB Output is correct
30 Correct 86 ms 33916 KB Output is correct
31 Correct 93 ms 33952 KB Output is correct
32 Correct 102 ms 34024 KB Output is correct
33 Correct 109 ms 34084 KB Output is correct
34 Correct 135 ms 40760 KB Output is correct
35 Correct 132 ms 40680 KB Output is correct
36 Correct 111 ms 40572 KB Output is correct
37 Correct 177 ms 40748 KB Output is correct
38 Correct 177 ms 40708 KB Output is correct
39 Correct 174 ms 40664 KB Output is correct
40 Correct 173 ms 40704 KB Output is correct
41 Correct 189 ms 40552 KB Output is correct
42 Correct 91 ms 34108 KB Output is correct
43 Correct 166 ms 40772 KB Output is correct
44 Correct 192 ms 40800 KB Output is correct
45 Correct 157 ms 40572 KB Output is correct
46 Correct 159 ms 40776 KB Output is correct

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11864 KB Output is correct
2 Correct 3 ms 11612 KB Output is correct
3 Correct 3 ms 11696 KB Output is correct
4 Correct 3 ms 11612 KB Output is correct
5 Incorrect 3 ms 11612 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11864 KB Output is correct
2 Correct 3 ms 11612 KB Output is correct
3 Correct 3 ms 11696 KB Output is correct
4 Correct 3 ms 11612 KB Output is correct
5 Incorrect 3 ms 11612 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11608 KB Output is correct
2 Correct 2 ms 11612 KB Output is correct
3 Correct 3 ms 11612 KB Output is correct
4 Correct 170 ms 41244 KB Output is correct
5 Correct 179 ms 41072 KB Output is correct
6 Correct 169 ms 41084 KB Output is correct
7 Correct 174 ms 41084 KB Output is correct
8 Correct 178 ms 41160 KB Output is correct
9 Correct 184 ms 41232 KB Output is correct
10 Correct 171 ms 41084 KB Output is correct
11 Correct 167 ms 41012 KB Output is correct
12 Correct 152 ms 40848 KB Output is correct
13 Correct 152 ms 40824 KB Output is correct
14 Correct 153 ms 40800 KB Output is correct
15 Correct 155 ms 40644 KB Output is correct
16 Correct 150 ms 40408 KB Output is correct
17 Correct 150 ms 40336 KB Output is correct
18 Correct 149 ms 40380 KB Output is correct
19 Correct 150 ms 40284 KB Output is correct
20 Correct 153 ms 40312 KB Output is correct
21 Correct 148 ms 40312 KB Output is correct
22 Correct 197 ms 40308 KB Output is correct
23 Correct 169 ms 40204 KB Output is correct
24 Correct 168 ms 40308 KB Output is correct
25 Correct 196 ms 40256 KB Output is correct
26 Correct 196 ms 40120 KB Output is correct
27 Correct 215 ms 40312 KB Output is correct
28 Correct 87 ms 34308 KB Output is correct
29 Correct 83 ms 34172 KB Output is correct
30 Correct 86 ms 33916 KB Output is correct
31 Correct 93 ms 33952 KB Output is correct
32 Correct 102 ms 34024 KB Output is correct
33 Correct 109 ms 34084 KB Output is correct
34 Correct 135 ms 40760 KB Output is correct
35 Correct 132 ms 40680 KB Output is correct
36 Correct 111 ms 40572 KB Output is correct
37 Correct 177 ms 40748 KB Output is correct
38 Correct 177 ms 40708 KB Output is correct
39 Correct 174 ms 40664 KB Output is correct
40 Correct 173 ms 40704 KB Output is correct
41 Correct 189 ms 40552 KB Output is correct
42 Correct 91 ms 34108 KB Output is correct
43 Correct 166 ms 40772 KB Output is correct
44 Correct 192 ms 40800 KB Output is correct
45 Correct 157 ms 40572 KB Output is correct
46 Correct 159 ms 40776 KB Output is correct
47 Correct 3 ms 11864 KB Output is correct
48 Correct 3 ms 11612 KB Output is correct
49 Correct 3 ms 11696 KB Output is correct
50 Correct 3 ms 11612 KB Output is correct
51 Incorrect 3 ms 11612 KB Output isn't correct
52 Halted 0 ms 0 KB -