제출 #1336714

#제출 시각아이디문제언어결과실행 시간메모리
1336714boclobanchatPort Facility (JOI17_port_facility)C++20
0 / 100
1 ms344 KiB
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e6+5;
const int mod=1e9+7;
const int INF=1e9;
int fen[MAXN],pos[MAXN],fx[MAXN],fy[MAXN],fl[MAXN],fr[MAXN];
int getlog(long long n) { return 63-__builtin_clzll(n); }
void update(int i,int n,int val) { for(;i<=n;i+=i&-i) fen[i]+=val; }
int get(int i) { int ans=0;for(;i;i-=i&-i) ans+=fen[i];return ans; }
void updatex(int i,int n,int val) { for(;i<=n;i+=i&-i) fx[i]=max(fx[i],val); }
int getx(int i) { int ans=0;for(;i;i-=i&-i) ans=max(ans,fx[i]);return ans; }
int walkx(int n,int val) { int ans=0;for(int i=getlog(n);i+1;i--) if(ans+(1<<i)<=n&&val>=fx[ans+(1<<i)]) ans+=(1<<i);return ans+1; }
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int l,r;
		cin>>l>>r;
		pos[r]=l,pos[l]=-r;
	}
	int f=n;
	for(int i=n*2;i;i--) if(pos[i]>0)
	{
		f-=get(i)-get(pos[i]);
		update(pos[i],n*2,1);
		updatex(pos[i],n*2,i);
	}
	else fl[i]=walkx(n*2,-pos[i]);
	for(int i=1;i<=n*2;i++) fen[i]=0,pos[i]=-pos[i];
	for(int i=1;i<=n*2;i++) if(pos[i]>0) updatex(n*2+1-pos[i],n*2,n*2+1-i);
	else fr[-pos[i]]=n*2+1-walkx(n*2,n*2+1+pos[i]);
	for(int i=1;i<=n*2;i++) for(int j=i+1;j<=n*2;j++) for(int k=j+1;k<=n*2;k++) if(pos[i]>0&&pos[j]>0&&pos[k]>0)
	{
		if(i<j&&j<pos[i]&&pos[i]<pos[j]) if(i<k&&k<pos[i]&&pos[i]<pos[k]) if(j<k&&k<pos[j]&&pos[j]<pos[k]) return cout<<0,0;
	}
//	for(int i=1;i<=n*2;i++) if(i<fl[i]&&fl[i]<fr[i]&&fr[i]<pos[i]) return cout<<0,0;
	int ans=1;
	for(int i=1;i<=f;i++) ans=ans*2%mod;
	cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...