oj.uz

Submission #415051

# Submission time Handle Problem Language Result Execution time Memory
415051 2021-05-31T13:24:53 Z 송준혁(#7511) Event Hopping 2 (JOI21_event2) C++17
0 / 100
 157 ms 15520 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define MOD 1000000007
#define INF (1ll<<62)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, M, K;
int S[101010], E[101010];
int L[101010], R[101010];
int P[20][101010];
pii V[101010];
vector<int> ans;
vector<pii> st;
set<pii> I;

int f(pii t){
	int u = lower_bound(L+1, L+M+1, t.fi)-L;
	int x = lower_bound(R+1, R+M+1, t.se+1)-R-1;
	if (u > x) return 0;
	int ret=1;
	for (int i=18; i>=0; i--) if (P[i][u] <= x) ret += (1<<i), u = P[i][u];
	return ret;
}

int main(){
	scanf("%d %d", &N, &K);
	for (int i=1; i<=N; i++){
		scanf("%d %d", &S[i], &E[i]);
		V[i] = pii(S[i], E[i]);
	}
	sort(V+1, V+N+1, [&](pii a, pii b){
		if (a.fi != b.fi) return a.fi < b.fi;
		return a.se > b.se;
	});
	for (int i=1; i<=N; i++){
		while (st.size() && st.back().se > V[i].se) st.pop_back();
		st.pb(V[i]);
	}
	M = st.size();
	int t=1;
	for (int i=1; i<=M; i++){
		tie(L[i], R[i])=st[i-1];
		while (t < i && R[t] <= L[i]) P[0][t] = i, t++;
	}
	while (t<=M+1) P[0][t] = M+1, t++; 
	for (int i=1; i<=18; i++) for (int j=1; j<=M+1; j++) P[i][j] = P[i-1][P[i-1][j]];
	I.insert(pii(0, MOD));
	int cnt = f(pii(0, MOD));
	for (int i=1; i<=N && K; i++){
		auto it = I.lower_bound(pii(S[i]+1, 0));
		if (it == I.begin()) continue;
		--it;
		if (it->se < E[i]) continue;
		pii l = pii(it->fi, S[i]);
		pii r = pii(E[i], it->se);
		if (cnt-f(*it)+f(l)+f(r) >= K-1){
			ans.pb(i), K--;
			I.erase(it);
			I.insert(l);
			I.insert(r);
		}
	}
	if (K) puts("-1");
	else for (int x : ans) printf("%d\n", x);
	return 0;
}

Compilation message

event2.cpp: In function 'int main()':
event2.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |  scanf("%d %d", &N, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~~
event2.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   scanf("%d %d", &S[i], &E[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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 Incorrect 157 ms 15520 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
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 2 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 Incorrect 1 ms 332 KB Output isn't correct
7 Halted 0 ms 0 KB -

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 2 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 Incorrect 1 ms 332 KB Output isn't correct
7 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 Incorrect 157 ms 15520 KB Output isn't correct
5 Halted 0 ms 0 KB -