Submission #60704166

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

using ll=long long;

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

#define INF 10000000
#define BT 512*1024*2
using P=pair<int,int>;
using PP=pair<P,int>;
using vi=vc<int>;

struct segtree1{
	int seg[BT],add[BT];
	int mum;

	void init(int n){
		mum=1;
		while(mum<n) mum<<=1;
		for(int i=0;i<mum*2;i++){
			seg[i]=INF;
			add[i]=0;
		}
	}
	void update(int a,int b,int k,int l,int r,int v){
		if(b<=l||r<=a) return;
		if(a<=l&&r<=b){
			seg[k]+=v;
			add[k]+=v;
		}
		else{
			update(a,b,k*2+1,l,(l+r)/2,v);
			update(a,b,k*2+2,(l+r)/2,r,v);
			seg[k]=min(seg[k*2+1],seg[k*2+2])+add[k];
		}
	}
	void update(int a,int b,int v){
		update(a,b,0,0,mum,v);
	}
	int get(int a,int b,int k,int l,int r){
		if(b<=l||r<=a) return INF;
		if(a<=l&&r<=b) return seg[k];
		else{
			int vl=get(a,b,k*2+1,l,(l+r)/2);
			int vr=get(a,b,k*2+2,(l+r)/2,r);
			return min(vl,vr)+add[k];
		}
	}
	int get(int a,int b){
		return get(a,b,0,0,mum);
	}
	int get(){
		return seg[0];
	}
}smn;
struct segtree2{
	int seg[BT],add[BT];
	int mum;

	void init(int n){
		mum=1;
		while(mum<n) mum<<=1;
		for(int i=0;i<mum*2;i++){
			seg[i]=-INF;
			add[i]=0;
		}
	}
	void update(int a,int b,int k,int l,int r,int v){
		if(b<=l||r<=a) return;
		if(a<=l&&r<=b){
			seg[k]+=v;
			add[k]+=v;
		}
		else{
			update(a,b,k*2+1,l,(l+r)/2,v);
			update(a,b,k*2+2,(l+r)/2,r,v);
			seg[k]=max(seg[k*2+1],seg[k*2+2])+add[k];
		}
	}
	void update(int a,int b,int v){
		update(a,b,0,0,mum,v);
	}
	int get(int a,int b,int k,int l,int r){
		if(b<=l||r<=a) return -INF;
		if(a<=l&&r<=b) return seg[k];
		else{
			int vl=get(a,b,k*2+1,l,(l+r)/2);
			int vr=get(a,b,k*2+2,(l+r)/2,r);
			return max(vl,vr)+add[k];
		}
	}
	int get(int a,int b){
		return get(a,b,0,0,mum);
	}
	int get(){
		return seg[0];
	}
}smx;
struct segtree3{
	int seg[BT];
	int mum;

	void init(int n){
		mum=1;
		while(mum<n) mum<<=1;
		for(int i=0;i<mum*2;i++) seg[i]=0;
	}
	void add(int k,int x){
		k+=mum-1;
		seg[k]=x;
		while(k>0){
			k=(k-1)/2;
			seg[k]=seg[k*2+1]+seg[k*2+2];
		}
	}
	int get(int a,int b,int k,int l,int r){
		if(b<=l||r<=a) return 0;
		if(a<=l&&r<=b) return seg[k];
		else{
			int vl=get(a,b,k*2+1,l,(l+r)/2);
			int vr=get(a,b,k*2+2,(l+r)/2,r);
			return vl+vr;
		}
	}
	int get(int a,int b){
		return get(a,b,0,0,mum);
	}
}scl,scr;

void solve(){
	int n;
	cin>>n;
	vc<int> L(n),R(n);
	int vl=0,vr=180005;
	vc<P> idl(n),idr(n);
	for(int i=0;i<n;i++){
		cin>>L[i]>>R[i];
		idl[i]=P(L[i],i);
		idr[i]=P(R[i],i);
	}
	sort(idl.begin(),idl.end());
	sort(idr.begin(),idr.end());

	smn.init(n+5);
	smx.init(n+5);
	scl.init(n+5);
	scr.init(n+5);
	int S=vr-1,T=vl;

	vc<int> al(n),ar(n);
	for(int i=0;i<n;i++){
		int p=lower_bound(idl.begin(),idl.end(),P(L[i],i))-idl.begin();
		int q=lower_bound(idr.begin(),idr.end(),P(R[i],i))-idr.begin();

		scl.add(p,1);
		scr.add(q,1);

		int c=scr.get(0,q+1);
		smn.update(q,q+1,R[i]-c-smn.get(q,q+1));
		smn.update(q+1,n+1,-1);

		int d=scl.get(p,n);
		smx.update(p,p+1,L[i]+d-smx.get(p,p+1));
		if(p>0) smx.update(0,p,1);

		int S=smn.get(),T=smx.get();
		if(T-S<=i) S=T-i-1;
		al[i]=S,ar[i]=T;
	}

	vc<vc<P>> dat(vr);
	for(int i=0;i<n;i++) dat[L[i]].pb(P(R[i],i));
	auto check=[&](int d)->bool{
		priority_queue <int,vector <int>, greater <int> > que;
		for(int i=0;i<vr;i++){
			if(!que.empty()){
				int t=que.top();que.pop();
				if(t<i) return false;
			}
			for(int j=0;j<dat[i].size();j++){
				if(dat[i][j].b<d) que.push(dat[i][j].a);
			}
		}
		if(!que.empty()) return false;
		return true;
	};

	int s=0,t=n+1;
	while(t-s>1){
		int d=(s+t)/2;
		if(check(d)) s=d;
		else t=d;
	}
	for(int i=0;i<s;i++) cout<<al[i]<<" "<<ar[i]<<endl;
	for(int i=s;i<n;i++) cout<<"Impossible"<<endl;
}
int main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	int T=1;
	while(T--) solve();
}

Submission Info

Compile Error

./Main.cpp:203:17: warning: comparison of integers of different signs: 'int' and 'size_type' (aka 'unsigned long') [-Wsign-compare]
                        for(int j=0;j<dat[i].size();j++){
                                    ~^~~~~~~~~~~~~~
./Main.cpp:171:6: warning: unused variable 'S' [-Wunused-variable]
        int S=vr-1,T=vl;
            ^
./Main.cpp:171:13: warning: unused variable 'T' [-Wunused-variable]
        int S=vr-1,T=vl;
                   ^
3 warnings generated.

Judge Result