This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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(){
//freopen("i.txt","r",stdin);
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+12,inf+12});
for(int x = 1;x <= n;x++){
int i = order[x];
range R = ranges[i];
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);
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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |