#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i,s,e) for(int i = s; i <= (int)e; ++i)
#define DEC(i,s,e) for(int i = s; i >= (int)e; --i)
#define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
#define db(x) cerr << #x << "=" << x << "\n"
#define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n"
#define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n"
#define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n"
#define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{" << ite.f << ',' << ite.s << "} "; cerr << "\n"
#define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n"
#define reach cerr << "LINE: " << __LINE__ << "\n";
#else
#define reach
#define db(x)
#define db2(x,y)
#define db3(a,b,c)
#define dbv(v)
#define dbvp(v)
#define dba(a,ss,ee)
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define f first
#define s second
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define g3(x) get<3>(x)
typedef pair <int, int> pi;
typedef tuple<int,int,int> ti3;
typedef tuple<int,int,int,int> ti4;
int rand(int a, int b) { return a + rng() % (b-a+1); }
const int MOD = 1e9 + 7;
const int inf = (int)1e9 + 500;
const long long oo = (long long)1e18 + 500;
template <typename T> void chmax(T& a, const T b) { a=max(a,b); }
template <typename T> void chmin(T& a, const T b) { a=min(a,b); }
const int MAXN = 100005;
typedef struct item *pitem;
struct item {
int prior;
array<int,3> val;
pitem l=nullptr, r=nullptr;
int cnt;
item(array<int,3> nval) {
val=nval;
prior=rng();
cnt = 0;
}
} *root, *done;
int cnt(pitem it) {
if(it==nullptr)return 0;
else return it->cnt;
}
void upd_cnt(pitem it){
if(it!=nullptr){
it->cnt=1+cnt(it->l)+cnt(it->r);
}
}
void merge(pitem &t, pitem l, pitem r) {
if(l==nullptr||r==nullptr){
t=l?l:r;
} else if(l->prior>r->prior){
merge(l->r,l->r,r);
t=l;
} else {
merge(r->l,l,r->l);
t=r;
}
upd_cnt(t);
}
void split(pitem t, pitem &l, pitem &r, array<int,3> key) {
if(t==nullptr){
l=nullptr;
r=nullptr;
return;
}
if(key<=t->val) { // split in left subtree
split(t->l,l,t->l,key);
r=t;
} else { // division is in the right subtree
split(t->r,t->r,r,key);
l=t;
}
upd_cnt(t);
}
array<int,3> rightmost(pitem t) {
if(t==nullptr)return {-1,-1,-1};
if(t->r!=nullptr)return rightmost(t->r);
else return t->val;
}
vector<int>out;
void print(pitem t) {
if(t==nullptr)return;
print(t->l);
out.pb(t->val[2]);
print(t->r);
}
int n,k;
int A[MAXN], B[MAXN];
array<int,3> Rr[MAXN];
map<int,int> tval;
void discretize(vector<int> V) {
vector<int> disc=V;
sort(all(disc));
disc.resize(unique(all(disc))-disc.begin());
FOR(i,0,V.size()-1){
int idx=lower_bound(all(disc),V[i])-disc.begin();
tval[V[i]]=idx+1;
}
}
bool in[MAXN];
int32_t main()
{
IAMSPEED
cin >> n >> k;
FOR(i,1,n) cin >> A[i] >> B[i];
vector<int> vec;
FOR(i,1,n) {
vec.pb(A[i]);
vec.pb(B[i]);
}
discretize(vec);
FOR(i,1,n){
Rr[i][0]=tval[A[i]];
Rr[i][1]=tval[B[i]];
Rr[i][2]=i;
}
sort(Rr+1,Rr+n+1,[&](array<int,3> x, array<int,3> y) {
return x[1]<y[1];
});
reach
int ans = 0;
int lst=0;
FOR(i,1,n){
if(Rr[i][0]>=lst){
lst=Rr[i][1];
pitem x= new item(Rr[i]);
merge(root,root,x);
}
}
if(cnt(root)<k)return cout << -1, 0;
sort(Rr+1,Rr+n+1,[&](array<int,3> x, array<int,3> y) {
return x[2]<y[2];
});
FOR(i,1,n) {
pitem lf,mid,rg;
split(done,lf,mid,array<int,3>({Rr[i][0],inf,inf}));//only the rightmost thing might be affected by me
split(mid,mid,rg,array<int,3>({Rr[i][1],0,0}));//rg is not affected by this
bool HAVE=!!cnt(mid);
array<int,3> cur=rightmost(lf);
HAVE|=(cur[1] > Rr[i][0]);
if(HAVE){
merge(lf,lf,mid);
merge(done,lf,rg);
continue;
}
// let us see if we can insert this range of [L[i],R[i]].
int SZ=cnt(root);
pitem L, M, R;
split(root,L,M,array<int,3>({Rr[i][0],inf,inf}));
split(M,M,R,array<int,3>({Rr[i][1],0,0}));
int sz=cnt(M);
array<int,3> c=rightmost(L);
if(c==Rr[i]){
pitem newnode=new item(Rr[i]);
merge(lf,lf,newnode);
merge(done,lf,rg);
merge(L,L,mid);
merge(root,L,R);
continue;
}
if(c[1] > Rr[i][0])++sz;
if(SZ-sz+1>=k) {
// delete M.
if(c[1]>Rr[i][0]){
split(L,L,M,c); // c is dumped into middle range
}
pitem nnode=new item(Rr[i]);
merge(L,L,nnode);
merge(root,L,R);
pitem newnode=new item(Rr[i]);
merge(lf,lf,newnode);
merge(done,lf,rg);
} else {
merge(L,L,mid);
merge(root,L,R);
merge(done,lf,rg);
}
}
out.clear();
print(root);
assert(cnt(root)>=k);
sort(all(out));
FOR(i,0,k-1)cout<<out[i]<<'\n';
}
Compilation message
event2.cpp: In function 'int32_t main()':
event2.cpp:142:6: warning: unused variable 'ans' [-Wunused-variable]
142 | int ans = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Runtime error |
235 ms |
64072 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Runtime error |
235 ms |
64072 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
