//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl '\n'
int n,k;
int aa[200001];
int bb[200001];
int ma=0;
//int tree[4*200001];
vector<int> pre[400001];
int re[400001][9];
/*void build(int no,int l,int r){
if(l==r){
if(mi[l]==-1){
tree[no]=2*n+1;
}
else{
tree[no]=mi[no];
}
}
else{
int mid=(l+r)/2;
build(no*2+1,l,mid);
build(no*2+2,mid+1,r);
tree[no]=min(tree[no*2+1],tree[no*2+2]);
}
}*/
int mi;
int cal(int aa,int bb){
int xx=mi;
if(aa>0){
xx=re[aa-1][0];
}
if(xx>bb){
return 0;
}
int ans2=1;
for(int j=17;j>=0;j--){
int cot;
if(j%2==0){
cot=re[xx][j/2];
}
else{
cot=re[re[xx][(j/2)]][(j/2)];
}
if(cot<=bb){
//cout<<xx<<":"<<j<<":"<<cot<<endl;
xx=cot;
ans2+=(1<<j);
}
}
return ans2;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;//>>k;
map<int,int> ss3;
mi=2*n;
for(int i=0;i<n;i++){
cin>>aa[i]>>bb[i];
//aa[i]*=2;
// aa[i]+=1;
// bb[i]*=2;
ss3[aa[i]]++;
ss3[bb[i]]++;
}
int ind=-1;
/*for(int i=0;i<2*n;i++){
tree[i]=2*n;
}*/
map<int,int> tt;
for(auto j:ss3){
ind++;
tt[j.a]=ind;
}
for(int i=0;i<n;i++){
aa[i]=tt[aa[i]];
ma=max(ma,aa[i]);
bb[i]=tt[bb[i]];
pre[aa[i]].pb(bb[i]);
/* if(mi[aa[i]]==-1){
mi[aa[i]]=bb[i];
}
mi[aa[i]]=min(mi[aa[i]],bb[i]);*/
}
/*for(int i=0;i<n;i++){
cout<<aa[i]<<":"<<bb[i]<<endl;
}*/
for(int i=2*n-1;i>=0;i--){
re[i][0]=mi;
for(auto j:pre[i]){
mi=min(mi,j);
}
}
for(int i=0;i<2*n;i++){
pre[i].clear();
}
for(int i=0;i<9;i++){
re[2*n][i]=2*n;
}
for(int j=1;j<9;j+=1){
for(int i=0;i<2*n;i++){
re[i][j]=re[i][j-1];
for(int k=0;k<3;k++){
re[i][j]=re[re[i][j]][j-1];
}
// re[i][j]=re[re[i][j-1]][j-1];
}
}
/* for(int i=0;i<n;i++){
cout<<re[i][0]<<",";
}
cout<<endl;*/
int cur=cal(0,2*n-1);
k=cur;
//cout<<cur<<":"<<endl;
if(cur<k){
cout<<-1<<endl;
return 0;
}
set<pair<int,int>> ss;
ss.insert({0,2*n-1});
vector<int> ans;
for(int i=0;i<n;i++){
if(ans.size()==k){
break;
}
auto j=ss.upper_bound({aa[i],2*n});
if(j==ss.begin()){
continue;
}
j--;
pair<int,int> no=*j;
if((aa[i]>=no.a and bb[i]<=no.b)){
//cout<<i<<"::"<<endl;
int cot=cur-cal(no.a,no.b);
if(no.a<aa[i]){
cot+=cal(no.a,aa[i]-1);
}
if(no.b>bb[i]){
cot+=cal(bb[i]+1,no.b);
}
cot+=1;
if(cot>=k){
cur=cot;
ans.pb(i);
ss.erase(no);
if(no.a<aa[i]){
ss.insert({no.a,aa[i]-1});
}
if(no.b>bb[i]){
ss.insert({bb[i]+1,no.b});
}
}
}
else{
continue;
}
}
cout<<ans.size()<<endl;
for(auto j:ans){
cout<<j+1<<" ";
}
return 0;
}
Compilation message
event2.cpp: In function 'int main()':
event2.cpp:140:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
140 | if(ans.size()==k){
| ~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
9708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
9708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
9708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
9708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
