Submission #197789

#	Time	Username	Problem	Language	Result	Execution time	Memory
197789		arnold518	Port Facility (JOI17_port_facility)	C++14	100 / 100	4710 ms	956368 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e6;
const ll MOD = 1e9+7;

struct Data
{
	int L, R;
};

int N, col[MAXN+10];
Data A[MAXN+10];
vector<int> adj[MAXN+10];

pii t[MAXN*2+10];
vector<pii> tree1[MAXN*8+10], tree2[MAXN*8+10];

void update1(int node, int tl, int tr)
{
	if(tl==tr)
	{
		if(t[tl].first!=-1) tree1[node].push_back(t[tl]);
		return;
	}
	int mid=tl+tr>>1;
	update1(node*2, tl, mid);
	update1(node*2+1, mid+1, tr);
	tree1[node].resize(tree1[node*2].size()+tree1[node*2+1].size());
	merge(tree1[node*2].begin(), tree1[node*2].end(), tree1[node*2+1].begin(), tree1[node*2+1].end(), tree1[node].begin(), greater<pii>());
}	

void query1(int node, int tl, int tr, int l, int r, int k)
{
	int i, j;
	if(r<tl || tr<l) return;
	if(l<=tl && tr<=r)
	{
		while(!tree1[node].empty() && tree1[node].back().first<l)
		{
			if(!col[tree1[node].back().second]) adj[k].push_back(tree1[node].back().second);
			tree1[node].pop_back();
		}
		return;
	}
	int mid=tl+tr>>1;
	query1(node*2, tl, mid, l, r, k);
	query1(node*2+1, mid+1, tr, l, r, k);
}

void update2(int node, int tl, int tr)
{
	if(tl==tr)
	{
		if(t[tl].first!=-1) tree2[node].push_back(t[tl]);
		return;
	}
	int mid=tl+tr>>1;
	update2(node*2, tl, mid);
	update2(node*2+1, mid+1, tr);
	tree2[node].resize(tree2[node*2].size()+tree2[node*2+1].size());
	merge(tree2[node*2].begin(), tree2[node*2].end(), tree2[node*2+1].begin(), tree2[node*2+1].end(), tree2[node].begin());
}	

void query2(int node, int tl, int tr, int l, int r, int k)
{
	int i, j;
	if(r<tl || tr<l) return;
	if(l<=tl && tr<=r)
	{
		while(!tree2[node].empty() && tree2[node].back().first>r)
		{
			if(!col[tree2[node].back().second]) adj[k].push_back(tree2[node].back().second);
			tree2[node].pop_back();
		}
		return;
	}
	int mid=tl+tr>>1;
	query2(node*2, tl, mid, l, r, k);
	query2(node*2+1, mid+1, tr, l, r, k);
}

int main()
{
	int i, j;
	scanf("%d", &N);
	for(i=1; i<=N; i++) scanf("%d%d", &A[i].L, &A[i].R);

	for(i=1; i<=2*N; i++) t[i]=pii(-1, -1);
	for(i=1; i<=N; i++) t[A[i].R]=pii(A[i].L, i);
	update1(1, 1, 2*N);
	
	for(i=1; i<=2*N; i++) t[i]=pii(-1, -1);
	for(i=1; i<=N; i++) t[A[i].L]=pii(A[i].R, i);
	update2(1, 1, 2*N);

	int cnt=0;
	for(i=1; i<=N; i++)
	{
		if(col[i]) continue;
		queue<int> Q;
		cnt++;

		Q.push(i); col[i]=1;
		while(!Q.empty())
		{
			int now=Q.front(); Q.pop();
			query1(1, 1, 2*N, A[now].L, A[now].R, now);
			query2(1, 1, 2*N, A[now].L, A[now].R, now);

			for(auto nxt : adj[now])
			{
				if(col[nxt]) continue;
				Q.push(nxt); col[nxt]=3-col[now];
			}
		}
	}

	vector<int> S[3];
	vector<pii> todo;
	for(i=1; i<=N; i++) todo.push_back({A[i].L, i}), todo.push_back({A[i].R, i+N});
	sort(todo.begin(), todo.end());

	for(auto it : todo)
	{
		if(it.second>N)
		{
			if(!S[1].empty() && S[1].back()==it.second-N) S[1].pop_back();
			else if(!S[2].empty() && S[2].back()==it.second-N) S[2].pop_back();
			else return !printf("0");
		}
		else
		{
			S[col[it.second]].push_back(it.second);
		}
	}

	ll ans=1;
	for(i=1; i<=cnt; i++) ans=ans*2%MOD;
	printf("%lld", ans);
}

Compilation message (stderr)

port_facility.cpp: In function 'void update1(int, int, int)':
port_facility.cpp:30:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
port_facility.cpp: In function 'void query1(int, int, int, int, int, int)':
port_facility.cpp:50:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
port_facility.cpp:39:6: warning: unused variable 'i' [-Wunused-variable]
  int i, j;
      ^
port_facility.cpp:39:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
port_facility.cpp: In function 'void update2(int, int, int)':
port_facility.cpp:62:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
port_facility.cpp: In function 'void query2(int, int, int, int, int, int)':
port_facility.cpp:82:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
port_facility.cpp:71:6: warning: unused variable 'i' [-Wunused-variable]
  int i, j;
      ^
port_facility.cpp:71:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
port_facility.cpp: In function 'int main()':
port_facility.cpp:89:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
port_facility.cpp:90:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
port_facility.cpp:91:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%d%d", &A[i].L, &A[i].R);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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