Submission #1197492

#TimeUsernameProblemLanguageResultExecution timeMemory
1197492mychecksedadEvent Hopping 2 (JOI21_event2)C++20
7 / 100
93 ms19368 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' #define ff first #define ss second #define pii pair<int,int> #define vi vector<int> const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30; int sz, T[N]; void build(){ for(int i = 0; i <= 2*sz + 1; ++i) T[i] = 0; } void upd(int v, int val){ v += sz; T[v] = max(T[v], val); for(v >>= 1; v > 0; v >>= 1) T[v] = max(T[v<<1], T[v<<1|1]); } int get(int l, int r){ l += sz; r += sz + 1; int res = 0; for(; l < r; l >>= 1, r >>= 1){ if(l&1) res = max(res, T[l++]); if(r&1) res = max(res, T[--r]); } return res; } int n, k; array<int, 3> a[N]; void solve(){ cin >> n >> k; vi val; for(int i = 1; i <= n; ++i){ cin >> a[i][1] >> a[i][0]; a[i][2] = i; val.pb(a[i][0]); val.pb(a[i][1]); a[i][0] = -a[i][0]; } val.pb(0); sort(all(val)); val.erase(unique(all(val)), val.end()); int m = val.size(); sort(a+1, a+1+n); for(int i = 1; i <= n; ++i){ swap(a[i][0], a[i][1]); a[i][1] = -a[i][1]; } sz = m; build(); vector<int> dp(m + 1); for(int i = 1; i <= n; ++i){ int L = lower_bound(all(val), a[i][0]) - val.begin(); int R = lower_bound(all(val), a[i][1]) - val.begin(); dp[L] = max(dp[L], get(R, m) + 1); upd(L, dp[L]); } vector<vector<array<int, 3>>> DP(n + 37); set<array<int, 3>> S, S2; for(int i = 1; i <= n; ++i){ int L = lower_bound(all(val), a[i][0]) - val.begin(); DP[dp[L]].pb({a[i][0], a[i][2], i}); if(dp[L] >= k){ S.insert({a[i][0], a[i][2], i}); S2.insert({a[i][2], a[i][0], i}); } } if(DP[k].empty()){ cout << -1; return; } int last = 0; vi res; for(int i = k; i >= 1; --i){ int mn = MOD, mnn = MOD; while(S.size() && (*S.begin())[0] < last){ auto u = (*S.begin()); S2.erase(array<int, 3>{u[1], u[0], u[2]}); S.erase(S.begin()); } auto [idx, _, j] = *S2.begin(); res.pb(idx); last = a[j][1]; S.erase(array<int, 3> {_, idx, j}); S2.erase(S2.begin()); for(auto f: DP[i-1]) { S.insert(f); S2.insert(array<int, 3>{f[1], f[0], f[2]}); } } sort(all(res)); for(int x: res) cout << x << '\n'; } int main(){ cin.tie(0); ios::sync_with_stdio(0); int tt = 1, aa; // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(tt--){ solve(); } cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n"; 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...