Submission #1792412

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n,t[100005],a[100005],b[100005];
#define s (1<<18)
int seg[s]={};
void update(int k,int a){
	k+=s/2-1; seg[k]=a;
	while(k>0){
		k=(k-1)/2;
		seg[k]=max(seg[k*2+1],seg[k*2+2]);
	}
}
int query(int a,int b,int k,int l,int r){
	if(r<a || b<l) return 0;
	if(a<=l && r<=b) return seg[k];
	else{
		int vl=query(a,b,k*2+1,l,(l+r)/2);
		int vr=query(a,b,k*2+2,(l+r)/2+1,r);
		return max(vl,vr);
	}
}
int main(){
	cin>>n;
	rep(i,n){
		cin>>a[i]>>b[i];
		t[a[i]]++; t[b[i]]--;
	}
	repn(i,100000) t[i] += t[i-1];
	repn(i,100000){
		update(i,t[i]);
	}
	int ans = INF;
	rep(i,n){
		int hoge = 0;
		hoge = max(hoge,query(1,a[i]-1,0,0,s/2-1));
		hoge = max(hoge,query(b[i],s/2-1,0,0,s/2-1));
		hoge = max(hoge,query(a[i],b[i]-1,0,0,s/2-1)-1);
		ans = min(ans,hoge);
	}
	cout << ans << endl;
}

Submission Info

Judge Result