Submission #893433

#TimeUsernameProblemLanguageResultExecution timeMemory
893433vjudge1Event Hopping 2 (JOI21_event2)C++17
8 / 100
60 ms23368 KiB
#include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() #define ar array #define pb push_back #define ln '\n' #define int long long using i64 = long long; template <class F, class _S> bool chmin(F &u, const _S &v){ bool flag = false; if ( u > v ){ u = v; flag |= true; } return flag; } template <class F, class _S> bool chmax(F &u, const _S &v){ bool flag = false; if ( u < v ){ u = v; flag |= true; } return flag; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; vector <int> L(n), R(n); for ( int i = 0; i < n; i++ ){ cin >> L[i] >> R[i]; } { // compression vector <int> p_; for ( int i = 0; i < n; i++ ){ p_.pb(L[i]); p_.pb(R[i]); } sort(all(p_)); p_.resize(unique(all(p_)) - p_.begin()); auto get = [&](int x){ return lower_bound(all(p_), x) - p_.begin() + 1; }; for ( int i = 0; i < n; i++ ){ L[i] = get(L[i]); R[i] = get(R[i]); } } int m = n * 2; vector <vector<int>> quL(m + 1), quR(m + 1); for ( int i = 0; i < n; i++ ){ quR[R[i]].pb(L[i]); quL[L[i]].pb(R[i]); } vector <int> dpL(m + 2), dpR(m + 1); for ( int i = m; i > 0; i-- ){ dpL[i] = dpL[i + 1]; for ( auto &j: quL[i] ){ chmax(dpL[i], dpL[j] + 1); } } for ( int i = 1; i <= m; i++ ){ dpR[i] = dpR[i - 1]; for ( auto &j: quR[i] ){ chmax(dpR[i], dpR[j] + 1); } } if ( dpL[1] < k ){ return cout << "-1\n", 0; } if ( n > 3e3 ){ int lst = -1; for ( int i = 0; i < n && k > 0; i++ ){ if ( lst <= L[i] && dpL[R[i]] >= k - 1 ){ cout << i + 1 << ln; k--; lst = R[i]; } } exit(0); } vector <ar<int,2>> rng; rng.pb({1, m}); int tot = 0; for ( int i = 0; i < n && tot < k; i++ ){ if ( dpR[L[i]] + dpL[R[i]] + 1 < k ){ continue; } int it = 0, j = -1; for ( auto &[l, r]: rng ){ if ( l <= L[i] && r >= R[i] ){ j = it; } it++; } if ( j != -1 ){ cout << i + 1 << ln; tot++; auto [l, r] = rng[j]; rng[j] = {l, L[i]}; rng.pb({R[i], r}); } } cout << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...