Submission #1321835

#TimeUsernameProblemLanguageResultExecution timeMemory
1321835PieArmyPort Facility (JOI17_port_facility)C++20
0 / 100
0 ms332 KiB
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)

struct Seg{
	int n;
	bool bad=false;
	vector<int>tree;
	vector<bool>lazy;
	void init(int N){
		n=N;
		tree.resize(n<<2,-1);
		lazy.resize(n<<2,0);
	}
	void push(int node,int left,int right){
		if(lazy[node]==0)return;
		if(tree[node]==2)bad=true;
		if(tree[node]!=-1)tree[node]=1;
		if(left!=right){
			lazy[node*2]=1;
			lazy[node*2+1]=1;
		}
		lazy[node]=0;
	}
	int l,r;
	void up(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left>=l&&right<=r){
			lazy[node]=1;
			push(node,left,right);
			return;
		}
		push(node,left,right);
		if(left>r||right<l)return;
		up(node*2,left,mid);
		up(node*2+1,mid+1,right);
		tree[node]=max(tree[node*2],tree[node*2+1]);
	}
	void update(int left,int right){
		l=left;r=right;
		if(l>r)return;
		up();
	}
	void dfs(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		push(node,left,right);
		if(left==right){
			tree[node]=r;
			return;
		}
		push(node*2,left,mid);
		push(node*2+1,mid+1,right);
		if(l>mid)dfs(node*2+1,mid+1,right);
		else dfs(node*2,left,mid);
		tree[node]=max(tree[node*2],tree[node*2+1]);
	}
	void yap(int tar,int val){
		l=tar;r=val;
		dfs();
	}
	int qu(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left>r||right<l)return -1;
		push(node,left,right);
		if(left>=l&&right<=r)return tree[node];
		return max(qu(node*2,left,mid),qu(node*2+1,mid+1,right));
	}
	int query(int left,int right){
		l=left;r=right;
		if(l>r)return -1;
		return qu();
	}
};

int n;
int a[1000023],b[1000023];
int arr[2000023];
int per[1000023],ind[1000023];
Seg seg,seg2;
int ans=1;
vector<int>v;

signed main(){
	ios_base::sync_with_stdio(23^23);cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
		arr[a[i]]=arr[b[i]]=i;
		per[i]=i;
	}
	seg.init(n);
	seg2.init(n);
	sort(per+1,per+n+1,[&](const int&x,const int&y){
		return b[x]>b[y];
	});
	for(int i=1;i<=n;i++){
		ind[per[i]]=i-1;
	}
	for(int i=1;i<=2*n;i++){
		int cur=arr[i];
		if(a[cur]==i){
			int once=seg.query(ind[cur]+1,n-1);
			//cerr<<cur<<": "<<ind[cur]<<endl;
			if(once==-1){
				seg.yap(ind[cur],0);
			}
			else{
				seg.yap(ind[cur],2);
				int bas=v[n-seg2.query(ind[cur],n-1)];
				//cerr<<cur<<" "<<bas<<endl;
				seg.update(ind[bas]+1,n-1);
				seg.update(ind[cur]+1,ind[bas]-1);
			}
			seg2.yap(ind[cur],n-(v.size()));
			v.pb(cur);
		}
		else{
			int x=seg.query(ind[cur],ind[cur]);
			seg2.yap(ind[cur],-1);
			if(x==0){
				ans*=2;
				if(ans>=1e9+7)ans-=1e9+7;
			}
			seg.yap(ind[cur],-1);
		}
	}
	for(int i=0;i<n;i++){
		seg.yap(i,-1);
	}
	if(seg.bad)ans=0;
	cout<<ans<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...