#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);(s<e?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct node{
int s,e,m;
int val=0;
node *l,*r;
node (int _s,int _e){
s=_s,e=_e,m=s+e>>1;
if (s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void update(int i,int k){
if (s==e) val=k;
else{
if (i<=m) l->update(i,k);
else r->update(i,k);
val=max(l->val,r->val);
}
}
int query(int i,int j){
if (s==i && e==j) return val;
else if (j<=m) return l->query(i,j);
else if (m<i) return r->query(i,j);
else return max(l->query(i,m),r->query(m+1,j));
}
} *root=new node(0,100005);
int n,k;
ii arr[100005];
ii sorted[100005];
int nxt[100005][20];
set<ii> s;
// we need to check if the intercept of all ranges is null
// find the range exactly after the tile
// then check the range exactly before it?
bool in(ii i){
auto it=s.ub(ii(i.se,-1));
if (it==s.begin()) return false;
return (*prev(it)).se>i.fi;
}
//we just need some way to find the max number of things we can take
//when we only allow taking stuff from a certain range
int calc(int l,int r){
int lo=-1,hi=n+1,mi;
while (hi-lo>1){
mi=hi+lo>>1;
if (root->query(0,mi)>=l) hi=mi;
else lo=mi;
}
int curr=hi;
if (sorted[curr].se>r) return 0;
int ans=1;
rep(x,20,0){
int temp=nxt[curr][x];
if (temp==-1) continue;
if (sorted[temp].se<=r) curr=temp,ans+=(1<<x);
}
return ans;
}
int main(){
cin.tie(0);
cout.tie(0);
cin.sync_with_stdio(false);
cin>>n>>k;
rep(x,0,n) cin>>arr[x].fi>>arr[x].se;
rep(x,0,n) sorted[x]=arr[x];
sort(sorted,sorted+n,[](ii i,ii j){
return i.se<j.se;
});
sorted[n]=ii(1e9+100,1e9+100);
//rep(x,0,n) cout<<sorted[x].fi<<" "<<sorted[x].se<<endl;
rep(x,0,n) root->update(x,sorted[x].fi);
root->update(n,1e9+100);
memset(nxt,-1,sizeof(nxt));
rep(x,0,n){
int lo=x,hi=n+1,mi;
while (hi-lo>1){
mi=hi+lo>>1;
if (root->query(x+1,mi)>=sorted[x].se) hi=mi;
else lo=mi;
}
nxt[x][0]=hi;
}
rep(x,n,0){
int curr=nxt[x][0];
rep(y,0,20){
if (curr==-1) break;
curr=nxt[x][y+1]=nxt[curr][y];
}
}
//rep(x,0,n) cout<<nxt[x][0]<<" "; cout<<endl;
int curr=calc(0,1e9);
if (curr<k){
cout<<"-1"<<endl;
return 0;
}
vector<int> ans;
s.insert(ii(0,0));
s.insert(ii(1e9,1e9));
rep(x,0,n){
if (!in(arr[x])){
auto iter=s.insert(arr[x]).fi;
int l=(*prev(iter)).se+1;
int r=(*next(iter)).fi;
int val=curr-calc(l,r)+calc(l,arr[x].fi)+calc(arr[x].se+1,r)+1;
//cout<<val<<endl;
//cout<<l<<" "<<arr[x].fi<<" "<<arr[x].se+1<<" "<<r<<endl;
if (val>=k){
ans.pub(x);
curr=val;
}
else{
s.erase(arr[x]);
}
}
//for (auto &it:s) cout<<it.fi<<"_"<<it.se<<" "; cout<<endl;
//cout<<endl;
}
rep(x,0,k) cout<<ans[x]<<endl;
}
Compilation message
event2.cpp: In constructor 'node::node(int, int)':
event2.cpp:29:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
29 | s=_s,e=_e,m=s+e>>1;
| ~^~
event2.cpp: In function 'int calc(int, int)':
event2.cpp:82:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
82 | mi=hi+lo>>1;
| ~~^~~
event2.cpp: In function 'int main()':
event2.cpp:123:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
123 | mi=hi+lo>>1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
17484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
17540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
17540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
17484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
