Submission #1210723

#TimeUsernameProblemLanguageResultExecution timeMemory
1210723PenguinsAreCuteEvent Hopping 2 (JOI21_event2)C++20
0 / 100
59 ms2744 KiB
#include <bits/stdc++.h> using namespace std; int main() { int n, k; cin >> n >> k; int l[n], r[n]; vector<int> u; for(int i=0;i<n;i++) { cin >> l[i] >> r[i]; u.push_back(l[i]); u.push_back(r[i]); } sort(u.begin(),u.end()); for(int i=0;i<n;i++) { l[i]=lower_bound(u.begin(),u.end(),l[i])-u.begin(); r[i]=lower_bound(u.begin(),u.end(),r[i])-u.begin(); } int dp[2*n+1]; dp[2*n]=0; int p=n-1; for(int i=2*n;i--;) { dp[i] = dp[i+1]; if(p!=-1&&i==l[p]) dp[i] = max(dp[i], dp[r[p--]] + 1); } if(dp[0] < k) { cout << -1; return 0; } int i=0; while(k) { if(dp[r[i]] >= k - 1) { cout << i+1 << "\n"; i = lower_bound(l,l+n,r[i])-l; k--; } else i++; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...