Submission #31056

#	Time	Username	Problem	Language	Result	Execution time	Memory
31056		zscoder	Port Facility (JOI17_port_facility)	C++14	78 / 100	6000 ms	648772 KiB

port_facility

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ll> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;

int s[1000001];
int e[1000001];
int pid[2000001];

const int MOD = 1e9 + 7;

int st1[23][2000001];
int st2[23][2000001];
int idx2[8000001];
int idx1[8000001];
int init[8000001];

void build(int id, int l, int r)
{
	if(r-l<2)
	{
		init[id]=idx1[id]=idx2[id]=l;
		return ;
	}
	int mid=(l+r)>>1;
	build(id*2,l,mid);
	build(id*2+1,mid,r);
	init[id] = idx1[id] = idx2[id] = init[id*2];
}

void add1(int id, int l, int r, int pos, int v, int d = 0)
{
	if(pos>=r||pos<l) return ;
	//cerr<<"ADD1 : "<<l<<' '<<r<<' '<<pos<<' '<<v<<'\n';
	st1[d][idx1[id]++] = v;
	if(r-l<2) return ;
	int mid=(l+r)>>1;
	add1(id*2,l,mid,pos,v,d+1);
	add1(id*2+1,mid,r,pos,v,d+1);
}

void add2(int id, int l, int r, int pos, int v, int d = 0)
{
	if(pos>=r||pos<l) return ;
	//cerr<<"ADD2 : "<<l<<' '<<r<<' '<<pos<<' '<<v<<'\n';
	st2[d][idx2[id]++] = v;
	if(r-l<2) return ;
	int mid=(l+r)>>1;
	add2(id*2,l,mid,pos,v,d+1);
	add2(id*2+1,mid,r,pos,v,d+1);
}

int col[1000001];
vi cur;

void get(int id, int l, int r, int ql, int qr, int d = 0)
{
	//cerr<<id<<' '<<l<<' '<<r<<' '<<ql<<' '<<qr<<'\n';
	if(ql>=r||l>=qr) return ;
	if(ql<=l&&r<=qr)
	{
		////cerr<<l<<' '<<r<<'\n';
		while(idx1[id]>init[id]&&st1[d][idx1[id]-1]>=qr)
		{
			//cerr<<pid[st1[id].back()]<<'\n';
			cur.pb(pid[st1[d][idx1[id]-1]]);
			idx1[id]--;
		}
		while(idx2[id]>init[id]&&st2[d][idx2[id]-1]<ql)
		{
			//cerr<<pid[st2[id].back()]<<'\n';
			cur.pb(pid[st2[d][idx2[id]-1]]);
			idx2[id]--;
		}
		return ;
	}
	int mid=(l+r)>>1;
	get(id*2,l,mid,ql,qr,d+1);
	get(id*2+1,mid,r,ql,qr,d+1);
}

int main()
{
	int n; scanf("%d",&n);
	for(int i = 0; i < n; i++)
	{
		scanf("%d %d",s+i,e+i);
		s[i]--; e[i]--;
		pid[s[i]]=i;
		pid[e[i]]=i;
	}
	build(1,0,2*n);
	for(int i = 0; i < 2*n; i++)
	{
		if(e[pid[i]] == i)
		{
			add1(1,0,2*n,s[pid[i]],e[pid[i]]);
		}
	}
	for(int i = 2*n - 1; i >= 0; i--)
	{
		if(s[pid[i]] == i)
		{
			add2(1,0,2*n,e[pid[i]],s[pid[i]]);
		}
	}
	ll ans=1;
	for(int i = 0; i < n; i++)
	{
		if(col[i]==0)
		{
			ans+=ans;
			while(ans>=MOD) ans-=MOD;
			queue<ii> q;
			q.push(mp(i,1));
			while(!q.empty())
			{
				int u=q.front().fi; int c = q.front().se;
				q.pop();
				if(col[u]!=0)
				{
					if(col[u]!=c)
					{
						printf("0\n");
						return 0;
					}
					continue;
				}
				col[u]=c;
				get(1,0,2*n,s[u],e[u]+1);
				while(!cur.empty())
				{
					q.push(mp(cur.back(),-c));
					cur.pop_back();
				}
			}
		}
	}
	printf("%lld\n",ans);
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:101:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n; scanf("%d",&n);
                       ^
port_facility.cpp:104:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",s+i,e+i);
                         ^

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 56 / 56
• Subtask 4: 0 / 22