Submission #30036

#TimeUsernameProblemLanguageResultExecution timeMemory
30036PrOAhMeTPort Facility (JOI17_port_facility)C++14
0 / 100
0 ms72332 KiB
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;

const int MAXN=1000005;
int n,ans=1,mod=1e9+7,col[2][MAXN*8],t1,t2,beg[MAXN*2];

void upd(int x,int l,int r,int ll,int v,int c) {

	if(l==ll&&r==ll) {
		col[c][x]+=v;
		return;
	}
	int md=(l+r)/2;
	if(ll<=md)
		upd(x*2,l,md,ll,v,c);
	else upd(x*2+1,md+1,r,ll,v,c);
	col[c][x]=col[c][x*2]+col[c][x*2+1];

}

int que(int x,int l,int r,int ll,int rr,int c) {

	if(l>rr||r<ll)
		return 0;
	if(l>=ll&&r<=rr)
		return col[c][x];
	int md=(l+r)/2;
	return que(x*2,l,md,ll,rr,c)+que(x*2+1,md+1,r,ll,rr,c);

}

void add(int x,int c) {

	upd(1,1,n+n,beg[x],-1,c);
	upd(1,1,n+n,x,1,c);

}

int main() {

	scanf("%d",&n);
	for(int i=1;i<=n;++i) {
		scanf("%d %d",&t1,&t2);
		beg[t2]=t1;
	}
	for(int i=1;i<=n+n;++i) {
		if(beg[i]==0)
			continue;
		t1=que(1,1,2*n,beg[i],i,0);
		t2=que(1,1,2*n,beg[i],i,1);
		//cout<<i<<" "<<beg[i]<<" "<<t1<<" "<<t2<<endl;
		if(t1&&t2) {
			cout<<0<<endl;
			return 0;
		}
		else if(t1==0&&t2==0) {
			ans=(ans*2)%mod;
			add(i,0);
		}
		else if(t1) {
			add(i,1);
		}
		else {
			add(i,0);
		}
	}
	printf("%d\n",ans);

}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:48:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
port_facility.cpp:50:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&t1,&t2);
                         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...