# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
417225 | 2021-06-03T13:31:49 Z | maomao90 | Event Hopping 2 (JOI21_event2) | C++17 | 67 ms | 17212 KB |
#include <bits/stdc++.h> using namespace std; template <class T> inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;} template <class T> inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;} #define REP(i, s, e) for (int i = s; i < e; i++) #define RREP(i, s, e) for (int i = s; i >= e; i--) typedef long long ll; typedef long double ld; #define MP make_pair #define FI first #define SE second typedef pair<int, int> ii; typedef pair<ll, ll> pll; #define MT make_tuple typedef tuple<int, int, int> iii; #define ALL(_a) _a.begin(), _a.end() #define pb emplace_back typedef vector<int> vi; typedef vector<ll> vll; typedef vector<ii> vii; #define INF 1000000005 #define LINF 1000000000000000005 #define MOD 1000000007 #define MAXN 200005 int n, k; ii lr[MAXN]; vi events; map<int, int> mp; vi adj[MAXN]; vi ans; int d[MAXN], p[MAXN];; void dfs(int u) { for (int v : adj[u]) { d[v] = d[u] + 1; p[v] = u; dfs(v); } } int main() { scanf("%d%d", &n, &k); REP (i, 0, n) { scanf("%d%d", &lr[i].FI, &lr[i].SE); } REP (i, 0, n) { if (events.empty() || lr[events.back()].FI != lr[i].FI || lr[events.back()].SE > lr[i].SE) { mp[lr[i].FI] = events.size(); events.pb(i); } } mp[INF] = events.size(); REP (i, 0, events.size()) { int r = lr[events[i]].SE; int nxt = mp.lower_bound(r) -> SE; adj[nxt].pb(i); } dfs(events.size()); int i = mp.begin() -> SE; while (1) { if (k == 0) break; int l = lr[events[i]].FI; for (; i >= 0 && lr[events[i]].FI == l; i--) { if (d[i] < k) { i++; if (lr[events[i]].FI != l) { printf("-1\n"); return 0; } ans.pb(events[i]); i = p[i]; break; } } if (i < 0 || lr[events[i]].FI <= l) { i++; ans.pb(events[i]); i = p[i]; } k--; } //assert(ans.size() == k); for (int i : ans) { printf("%d\n", i + 1); } //REP (i, 0, events.size() + 1) { //printf("%d:", i); //for (int v : adj[i]) { //printf(" %d", v); //} //printf("\n"); //} } /* 4 2 1 4 3 5 4 9 7 10 8 3 1 4 1 3 1 2 3 8 3 5 6 11 6 10 6 7 */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4940 KB | Output is correct |
2 | Correct | 3 ms | 4940 KB | Output is correct |
3 | Correct | 3 ms | 4940 KB | Output is correct |
4 | Incorrect | 67 ms | 17212 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4940 KB | Output is correct |
2 | Correct | 4 ms | 4940 KB | Output is correct |
3 | Incorrect | 3 ms | 4940 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4940 KB | Output is correct |
2 | Correct | 4 ms | 4940 KB | Output is correct |
3 | Incorrect | 3 ms | 4940 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4940 KB | Output is correct |
2 | Correct | 3 ms | 4940 KB | Output is correct |
3 | Correct | 3 ms | 4940 KB | Output is correct |
4 | Incorrect | 67 ms | 17212 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |