Submission #393020

#TimeUsernameProblemLanguageResultExecution timeMemory
393020oolimryEvent Hopping 2 (JOI21_event2)C++17
1 / 100
1969 ms23132 KiB
#include <bits/stdc++.h> using namespace std; #define all(x) (x).begin(), (x).end() #define sz(x) ((int) x.size()) #define show(x) cerr << #x << " is " << x << endl; #define show2(x, y) cerr << #x << " is " << x << ", " << #y << " is " << y << endl; typedef long long lint; typedef pair<lint, lint> ii; const lint inf = 0x3f3f3f3f; struct range{ int l, r, id; }; vector<range> ranges; int p[19][200005]; int order[200005]; set<ii> taken; lint solve(lint s, lint limit){ if(ranges[s].r > limit) return 0; lint res = 0; for(int k = 18;k >= 0;k--){ int ns = p[k][s]; if(ranges[ns].r <= limit){ res += (1<<k); s = ns; } } return res+1; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n, K; cin >> n >> K; for(int i = 1;i <= n;i++){ int l, r; cin >> l >> r; ranges.push_back({l,r,i}); } ranges.push_back({inf+10, inf+10, n}); sort(all(ranges), [&](range a, range b){ return a.r < b.r; }); for(int i = 0;i <= 18;i++) fill(p[i], p[i]+n+1, n); set<ii> S; for(int i = 0;i < n;i++){ range R = ranges[i]; while(!S.empty()){ auto it = S.begin(); if(it->first <= R.l){ p[0][it->second] = i; S.erase(it); } else break; } S.insert({R.r,i}); order[R.id] = i; } for(int k = 1;k <= 18;k++){ for(int i = 0;i < n;i++) p[k][i] = p[k-1][p[k-1][i]]; } vector<int> ans; int cnt = solve(0, inf-2); if(cnt < K){ cout << -1; return 0; } taken.insert({inf,inf}); for(int x = 1;x <= n;x++){ int i = order[x]; range R = ranges[i]; show2(R.l, R.r); auto nxt = taken.lower_bound({R.r, -1}); int s = 0; if(nxt != taken.begin()){ auto pre = prev(nxt); int pid = pre->second; if(ranges[pid].r > R.l) continue; s = p[0][pid]; } else s = 0; int newcnt = cnt; newcnt += solve(s, R.l); newcnt += solve(i, nxt->first); newcnt -= solve(s, nxt->first); show(newcnt); if(newcnt >= K){ ans.push_back(R.id); taken.insert({R.l, i}); } } for(int i = 0;i < K;i++) cout << ans[i] << "\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...