oj.uz

답안 #393023

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
393023 2021-04-22T14:49:53 Z oolimry Event Hopping 2 (JOI21_event2) C++17
1 / 100
 104 ms 16140 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(){
	//freopen("i.txt","r",stdin);
	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];
		
		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);
		
		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

# 결과 실행 시간 메모리 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 97 ms 16140 KB Output is correct
5 Correct 103 ms 16120 KB Output is correct
6 Correct 97 ms 16048 KB Output is correct
7 Correct 100 ms 15916 KB Output is correct
8 Correct 98 ms 16056 KB Output is correct
9 Correct 104 ms 16056 KB Output is correct
10 Correct 97 ms 16008 KB Output is correct
11 Correct 95 ms 16004 KB Output is correct
12 Correct 78 ms 13572 KB Output is correct
13 Correct 77 ms 13508 KB Output is correct
14 Correct 77 ms 13492 KB Output is correct
15 Correct 76 ms 13492 KB Output is correct
16 Correct 72 ms 10324 KB Output is correct
17 Correct 55 ms 10276 KB Output is correct
18 Correct 70 ms 10164 KB Output is correct
19 Correct 49 ms 9512 KB Output is correct
20 Incorrect 50 ms 9444 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #2
1.0 / 1.0

# 결과 실행 시간 메모리 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 332 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 332 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 332 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 336 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 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

# 결과 실행 시간 메모리 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 332 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 332 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 332 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 336 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 3 ms 716 KB Output is correct
29 Incorrect 2 ms 716 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# 결과 실행 시간 메모리 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 97 ms 16140 KB Output is correct
5 Correct 103 ms 16120 KB Output is correct
6 Correct 97 ms 16048 KB Output is correct
7 Correct 100 ms 15916 KB Output is correct
8 Correct 98 ms 16056 KB Output is correct
9 Correct 104 ms 16056 KB Output is correct
10 Correct 97 ms 16008 KB Output is correct
11 Correct 95 ms 16004 KB Output is correct
12 Correct 78 ms 13572 KB Output is correct
13 Correct 77 ms 13508 KB Output is correct
14 Correct 77 ms 13492 KB Output is correct
15 Correct 76 ms 13492 KB Output is correct
16 Correct 72 ms 10324 KB Output is correct
17 Correct 55 ms 10276 KB Output is correct
18 Correct 70 ms 10164 KB Output is correct
19 Correct 49 ms 9512 KB Output is correct
20 Incorrect 50 ms 9444 KB Output isn't correct
21 Halted 0 ms 0 KB -