oj.uz

Submission #393020

# Submission time Handle Problem Language Result Execution time Memory
393020 2021-04-22T14:48:45 Z oolimry Event Hopping 2 (JOI21_event2) C++17
1 / 100
 1969 ms 23132 KB 
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x, y) cerr << #x << " is " << x << ", " << #y << " is " << y << endl;
typedef long long lint;
typedef pair<lint, lint> ii;

const lint inf = 0x3f3f3f3f;
struct range{ int l, r, id; };
vector<range> ranges;

int p[19][200005];
int order[200005];

set<ii> taken;

lint solve(lint s, lint limit){
	if(ranges[s].r > limit) return 0;
	lint res = 0;
	for(int k = 18;k >= 0;k--){
		int ns = p[k][s];
		if(ranges[ns].r <= limit){
			res += (1<<k);
			s = ns;
		}
	}
	return res+1;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n, K; cin >> n >> K;
	for(int i = 1;i <= n;i++){
		int l, r; cin >> l >> r;
		ranges.push_back({l,r,i});
	}
	
	ranges.push_back({inf+10, inf+10, n});
	sort(all(ranges), [&](range a, range b){ return a.r < b.r; });
	for(int i = 0;i <= 18;i++) fill(p[i], p[i]+n+1, n);
	
	set<ii> S;
	
	for(int i = 0;i < n;i++){
		range R = ranges[i];
		while(!S.empty()){
			auto it = S.begin();
			if(it->first <= R.l){
				p[0][it->second] = i;
				S.erase(it);
			}
			else break;
		}
		S.insert({R.r,i});
		order[R.id] = i;
	}
	
	for(int k = 1;k <= 18;k++){
		for(int i = 0;i < n;i++) p[k][i] = p[k-1][p[k-1][i]];
	}
	
	vector<int> ans;
	int cnt = solve(0, inf-2);
	
	if(cnt < K){
		cout << -1; return 0;
	}
	
	taken.insert({inf,inf});
	
	for(int x = 1;x <= n;x++){
		int i = order[x];
		range R = ranges[i];
		show2(R.l, R.r);
		
		auto nxt = taken.lower_bound({R.r, -1});
		int s = 0;
		if(nxt != taken.begin()){
			auto pre = prev(nxt);
			int pid = pre->second;
			if(ranges[pid].r > R.l) continue;
			
			s = p[0][pid];
		}
		else s = 0;

		int newcnt = cnt;
		newcnt += solve(s, R.l);
		newcnt += solve(i, nxt->first);
		newcnt -= solve(s, nxt->first);
		
		show(newcnt);
		if(newcnt >= K){
			ans.push_back(R.id);
			taken.insert({R.l, i});
		}
	}
	
	for(int i = 0;i < K;i++) cout << ans[i] << "\n";
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1935 ms 23132 KB Output is correct
5 Correct 1923 ms 23032 KB Output is correct
6 Correct 1969 ms 22988 KB Output is correct
7 Correct 1933 ms 23052 KB Output is correct
8 Correct 1947 ms 23020 KB Output is correct
9 Correct 1936 ms 23008 KB Output is correct
10 Correct 1931 ms 23048 KB Output is correct
11 Correct 1961 ms 23016 KB Output is correct
12 Correct 1675 ms 19968 KB Output is correct
13 Correct 1714 ms 19920 KB Output is correct
14 Correct 1715 ms 19892 KB Output is correct
15 Correct 1704 ms 19896 KB Output is correct
16 Correct 1381 ms 16084 KB Output is correct
17 Correct 1390 ms 15836 KB Output is correct
18 Correct 1353 ms 15804 KB Output is correct
19 Correct 1313 ms 15136 KB Output is correct
20 Incorrect 1315 ms 14956 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 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 41 ms 848 KB Output is correct
29 Incorrect 39 ms 844 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1935 ms 23132 KB Output is correct
5 Correct 1923 ms 23032 KB Output is correct
6 Correct 1969 ms 22988 KB Output is correct
7 Correct 1933 ms 23052 KB Output is correct
8 Correct 1947 ms 23020 KB Output is correct
9 Correct 1936 ms 23008 KB Output is correct
10 Correct 1931 ms 23048 KB Output is correct
11 Correct 1961 ms 23016 KB Output is correct
12 Correct 1675 ms 19968 KB Output is correct
13 Correct 1714 ms 19920 KB Output is correct
14 Correct 1715 ms 19892 KB Output is correct
15 Correct 1704 ms 19896 KB Output is correct
16 Correct 1381 ms 16084 KB Output is correct
17 Correct 1390 ms 15836 KB Output is correct
18 Correct 1353 ms 15804 KB Output is correct
19 Correct 1313 ms 15136 KB Output is correct
20 Incorrect 1315 ms 14956 KB Output isn't correct
21 Halted 0 ms 0 KB -