제출 #1172586

#제출 시각아이디문제언어결과실행 시간메모리
1172586jj_masterEvent Hopping 2 (JOI21_event2)C++20
100 / 100
243 ms42276 KiB
// USACO #include <bits/stdc++.h> using namespace std; int n, k; int a[200001], b[200001]; int ma = 0; vector<int> pre[400001]; int re[400001][9]; int mi; int cal(int a, int b) { int xx = mi; if(a > 0) { xx = re[a - 1][0]; } if(xx > b) { return 0; } int ans2 = 1; for(int j = 17; j >= 0; j--) { int cot; if(j % 2 == 0) { cot = re[xx][j / 2]; } else { cot = re[re[xx][(j / 2)]][(j / 2)]; } if(cot <= b) { xx = cot; ans2 += (1 << j); } } return ans2; } void sol() { cin >> n >> k; map<int, int> ss3; mi = 2 * n; for(int i = 0 ; i < n; i++) { cin >> a[i] >> b[i]; a[i] *= 2; a[i] += 1; b[i] *= 2; ss3[a[i]]++; ss3[b[i]]++; } int ind = -1; map<int, int> tt; for(auto j : ss3) { ind++; tt[j.first] = ind; } for(int i = 0; i < n; i++) { a[i] = tt[a[i]]; ma = max(ma, a[i]); b[i] = tt[b[i]]; pre[a[i]].push_back(b[i]); } for(int i = 2 * n - 1; i >= 0; i--) { re[i][0] = mi; for(auto j : pre[i]) { mi = min (mi, j); } } for(int i = 0; i < 2 * n; i++) { pre[i].clear(); } for(int i = 0; i < 9; i++) { re[2 * n][i] = 2 * n; } for(int j = 1; j < 9; j++) { for(int i = 0; i < 2 * n; i++) { re[i][j] = re[i][j - 1]; for(int k = 0; k < 3; k++) { re[i][j] = re[re[i][j]][j - 1]; } } } int cur = cal(0, 2 * n - 1); if(cur < k) { cout << -1 << "\n"; } set<pair<int, int>> ss; ss.insert({0, 2 * n - 1}); vector<int> ans; for(int i = 0;i < n; i++) { if(ans.size() == k) { break; } auto j = ss.upper_bound({a[i], 2*n}); if(j == ss.begin()) { continue; } j--; pair<int, int> no=*j; if((a[i] >= no.first && b[i] <= no.second)) { int cot = cur - cal(no.first, no.second); if(no.first < a[i]) { cot += cal(no.first, a[i] - 1); } if(no.second > b[i]) { cot += cal(b[i] + 1, no.second); } cot += 1; if(cot >= k) { cur = cot; ans.push_back(i); ss.erase(no); if(no.first < a[i]) { ss.insert({no.first, a[i] - 1}); } if(no.second > b[i]) { ss.insert({b[i] + 1, no.second}); } } } else { continue; } } for(auto j : ans){ cout<< j + 1 << "\n"; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); sol(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...