# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
722534 | 2023-04-12T08:30:34 Z | minhnhatnoe | Event Hopping 2 (JOI21_event2) | C++14 | 3000 ms | 1876 KB |
#define _GLIBCXX_DEBUG #include <bits/stdc++.h> using namespace std; typedef long long ll; vector<int> l; struct node{ int left, right; int idx; }; vector<int> pos; vector<node> a; int test(int l, int r){ int cnt = 0; int ptr = 0; for (int i=0; i<a.size(); i++){ if (a[i].idx == -1) continue; if (l <= a[i].left && a[i].left < r) continue; if (l < a[i].right && a[i].right <= r) continue; if (a[i].left < ptr) continue; cnt++; ptr = a[i].right; } return cnt; } void erase_inter(int l, int r){ vector<node> nxta; for (int i=0; i<a.size(); i++){ if (l <= a[i].left && a[i].left < r) continue; if (l < a[i].right && a[i].right <= r) continue; nxta.push_back(a[i]); } a = move(nxta); } signed main(){ cin.tie(0)->sync_with_stdio(0); int n, k; cin >> n >> k; l.resize(n), a.resize(n); for (int i=0; i<n; i++){ cin >> a[i].left >> a[i].right; a[i].idx = i; l[i] = a[i].left; } sort(l.begin(), l.end()); l.resize(unique(l.begin(), l.end()) - l.begin()); for (int i=0; i<a.size(); i++){ a[i].left = lower_bound(l.begin(), l.end(), a[i].left) - l.begin(); a[i].right = lower_bound(l.begin(), l.end(), a[i].right) - l.begin(); } sort(a.begin(), a.end(), [](const node &x, const node &y){ return x.right < y.right; }); if (test(-1, -1) < k){ cout << "-1\n"; return 0; } while (k){ pos.assign(n, -1); for (int i=0; i<a.size(); i++){ if (a[i].idx == -1) continue; pos[a[i].idx] = i; } for (int i=0; i<pos.size(); i++){ if (pos[i] == -1) continue; if (test(a[pos[i]].left, a[pos[i]].right) + 1 < k){ a[pos[i]].idx = -1; continue; } a[pos[i]].idx = -1; erase_inter(a[pos[i]].left, a[pos[i]].right); cout << i+1 << "\n"; break; } k--; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Execution timed out | 3050 ms | 1876 KB | Time limit exceeded |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Incorrect | 1 ms | 212 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Incorrect | 1 ms | 212 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Execution timed out | 3050 ms | 1876 KB | Time limit exceeded |
5 | Halted | 0 ms | 0 KB | - |