#include <bits/stdc++.h>
using namespace std;
#define int long long
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = 200005;
const int inf=1000000500ll;
const int oo =1000000000000000000ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi;
int n,k;
array<int,3> A[MAXN];
int rtwok[MAXN][20];
int ltwok[MAXN][20];
struct node1 {
int s,e,m,val;
node1 *l, *r;
node1 (int _s, int _e){
s=_s;e=_e;m=(s+e)/2;
val=inf;
if(s!=e){
l=new node1(s,m);
r=new node1(m+1,e);
}
}
void update(int x, int nval){
if(s==e){
val=nval;
return;
}
if(x>m)r->update(x,nval);
else l->update(x,nval);
val=min(l->val,r->val);
}
int query(int x, int y){
if(s==x&&e==y){
return val;
}
if(x>m)return r->query(x,y);
else if(y<=m)return l->query(x,y);
else return min(l->query(x,m), r->query(m+1,y));
}
}*mnseg;
struct node2{
int s,e,m,val;
node2 *l, *r;
node2 (int _s, int _e){
s=_s;e=_e;m=(s+e)/2;
val=-1;
if(s!=e){
l=new node2(s,m);
r=new node2(m+1,e);
}
}
void update(int x, int nval){
if(s==e){
val=nval;
return;
}
if(x>m)r->update(x,nval);
else l->update(x,nval);
val=max(l->val,r->val);
}
int query(int x, int y){
if(s==x&&e==y){
return val;
}
if(x>m)return r->query(x,y);
else if(y<=m)return l->query(x,y);
else return max(l->query(x,m), r->query(m+1,y));
}
}*mxseg;
map<int,int> to_n;
map<int,int> to_1;
struct fenw {
int fw[MAXN], fw2[MAXN];
void update(int x, int y, int v) { //inclusive
for (int tx=x; tx < MAXN; tx += tx&(-tx)) fw[tx] += v, fw2[tx] -= v*(x-1);
for (int ty=y+1; ty < MAXN; ty += ty&(-ty)) fw[ty] -= v, fw2[ty] += v*y;
}
int sum (int x) {
int res = 0;
for (int tx=x; tx; tx -= tx&(-tx)) res += fw[tx]*x + fw2[tx];
return res;
}
int range_sum(int x, int y) { //inclusive
return sum(y)-sum(x-1);
}
}fw;
map<int,int> mapper;
int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> k;
int m=2*n+2;
memset(rtwok,-1,sizeof rtwok);
memset(ltwok,-1,sizeof ltwok);
mnseg=new node1(0,m);
mxseg=new node2(0,m);
vector<pair<int,int>> in;
vector<int> disc;
for(int i=1;i<=n;i++){
int a,b; cin >> a >> b;
in.push_back({a,b});
disc.push_back(a);
disc.push_back(b);
}
sort(disc.begin(),disc.end());
disc.resize(unique(disc.begin(),disc.end())-disc.begin());
for(int i=0;i<(int)disc.size();i++){
mapper[disc[i]]=i+1;
}
for(int i=1;i<=n;i++){
A[i][0] = mapper[in[i-1].first];
A[i][1] = mapper[in[i-1].second];
A[i][2] = i;
}
for(int i=1;i<=n;i++){
mnseg->update(A[i][0],A[i][1]);
mxseg->update(A[i][1],A[i][0]);
}
for(int i=1;i<=m;i++){
rtwok[i][0]=mnseg->query(i,m);
if(rtwok[i][0]==inf)rtwok[i][0]=-1;
ltwok[i][0]=mxseg->query(1,i);
}
for(int i=m;i>=1;i--){
for(int j=1;j<=19;j++){
if(rtwok[i][j-1] == -1)continue;
rtwok[i][j]=rtwok[rtwok[i][j-1]][j-1];
}
}
for(int i=1;i<=m;i++){
for(int j=1;j<=19;++j){
if(ltwok[i][j-1]==-1)continue;
ltwok[i][j]=ltwok[ltwok[i][j-1]][j-1];
}
}
vector<int>out;
for(int i=1;i<=n;i++){
int L=A[i][0], R=A[i][1];
if(fw.range_sum(L+1,R-1)>0){
continue;
}
auto it=to_n.lower_bound(R);
pair<int,int> gn={m+1,0};
if(it!=to_n.end())gn=*it;
int sum = 1;
int sumL = 0, sumR=0;
for(int k=19;k>=0;k--){
if(rtwok[R][k] != -1 && rtwok[R][k] <= gn.first){
R=rtwok[R][k];
sum+=(1<<k);
sumR+=(1<<k);
}
}
sumR+=gn.second;
sum+=gn.second;
it=to_1.upper_bound(L);
pair<int,int> g1={0,0};
if(it!=to_1.begin())g1=*prev(it);
for(int k=19;k>=0;k--){
if(ltwok[L][k] != -1 && ltwok[L][k] >= g1.first){
L=ltwok[L][k];
sum+=(1<<k);
sumL+=(1<<k);
}
}
sumL+=g1.second;
sum+=g1.second;
if(sum>=k && (int)out.size()<k){
out.push_back(i);
fw.update(A[i][0],A[i][1],1);
to_n[A[i][0]]=1+sumR;
to_1[A[i][1]]=1+sumL;
}
}
if(out.empty())cout<<-1<<'\n';
else{
assert((int)out.size()==k);
for(auto x:out)cout<<x<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
62932 KB |
Output is correct |
| 2 |
Correct |
22 ms |
62932 KB |
Output is correct |
| 3 |
Correct |
21 ms |
62932 KB |
Output is correct |
| 4 |
Incorrect |
304 ms |
147028 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
63036 KB |
Output is correct |
| 2 |
Correct |
21 ms |
62904 KB |
Output is correct |
| 3 |
Correct |
21 ms |
62932 KB |
Output is correct |
| 4 |
Correct |
21 ms |
62932 KB |
Output is correct |
| 5 |
Correct |
21 ms |
63080 KB |
Output is correct |
| 6 |
Correct |
21 ms |
63060 KB |
Output is correct |
| 7 |
Correct |
23 ms |
63060 KB |
Output is correct |
| 8 |
Incorrect |
22 ms |
63008 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
63036 KB |
Output is correct |
| 2 |
Correct |
21 ms |
62904 KB |
Output is correct |
| 3 |
Correct |
21 ms |
62932 KB |
Output is correct |
| 4 |
Correct |
21 ms |
62932 KB |
Output is correct |
| 5 |
Correct |
21 ms |
63080 KB |
Output is correct |
| 6 |
Correct |
21 ms |
63060 KB |
Output is correct |
| 7 |
Correct |
23 ms |
63060 KB |
Output is correct |
| 8 |
Incorrect |
22 ms |
63008 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
62932 KB |
Output is correct |
| 2 |
Correct |
22 ms |
62932 KB |
Output is correct |
| 3 |
Correct |
21 ms |
62932 KB |
Output is correct |
| 4 |
Incorrect |
304 ms |
147028 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
