Submission #727340

#	Time	Username	Problem	Language	Result	Execution time	Memory
727340		sunwukong123	Event Hopping 2 (JOI21_event2)	C++14	0 / 100	185 ms	64136 KiB

event2

#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(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(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 (stderr)

event2.cpp: In function 'int32_t main()':
event2.cpp:142:6: warning: unused variable 'ans' [-Wunused-variable]
  142 |  int ans = 0;
      |      ^~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 1
• Subtask 3: 0 / 31
• Subtask 4: 0 / 61