Submission #79488

#	Time	Username	Problem	Language	Result	Execution time	Memory
79488		Plurm	Port Facility (JOI17_port_facility)	C++11	0 / 100	532 ms	587488 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
vector<int> g[1000005];
int col[1000005];
bool dfs(int u,int p = -1,int c = 1){
	col[u] = c;
	c = c % 2 + 1;
	for(int v : g[u]){
		if(v == p) continue;
		if(col[v] && col[v] != c) return false;
		if(col[v]) continue;
		if(!dfs(v,u,c)) return false;
	}
	return true;
}
int segT[8000005];
int lb[8000005];
int rb[8000005];
vector<int> cmpsegT[8000005];
vector<int> cmpsegTmn[8000005];
vector<int> cmpsegTmx[8000005];
vector<pair<int,int> > pts;
void build(int c,int l,int r){
	lb[c] = l;
	rb[c] = r;
	if(l == r){
		segT[c] = pts[l].first;
		cmpsegT[c].push_back(0);
		cmpsegT[c].push_back(pts[l].first);
		cmpsegTmx[c].push_back(0);
		cmpsegTmx[c].push_back(-1);
		cmpsegTmn[c].push_back(0);
		cmpsegTmn[c].push_back(2);
		return;
	}
	int k = (l + r)/2;
	build(2*c,l,k);
	build(2*c+1,k+1,r);
	segT[c] = min(segT[2*c],segT[2*c+1]);
	int ll = 1;
	int rr = 1;
	cmpsegT[c].push_back(0);
	cmpsegTmx[c].push_back(0);
	cmpsegTmn[c].push_back(0);
	while(ll < cmpsegT[2*c].size() && rr < cmpsegT[2*c+1].size()){
		if(cmpsegT[2*c][ll] < cmpsegT[2*c+1][rr]){
			cmpsegT[c].push_back(cmpsegT[2*c][ll]);
			cmpsegTmx[c].push_back(-1);
			cmpsegTmn[c].push_back(2);
			ll++;
		}else{
			cmpsegT[c].push_back(cmpsegT[2*c+1][rr]);
			cmpsegTmx[c].push_back(-1);
			cmpsegTmn[c].push_back(2);
			rr++;
		}
	}
	while(ll < cmpsegT[2*c].size()){
		cmpsegT[c].push_back(cmpsegT[2*c][ll]);
		cmpsegTmx[c].push_back(-1);
		cmpsegTmn[c].push_back(2);
		ll++;
	}
	while(rr < cmpsegT[2*c+1].size()){
		cmpsegT[c].push_back(cmpsegT[2*c+1][rr]);
		cmpsegTmx[c].push_back(-1);
		cmpsegTmn[c].push_back(2);
		rr++;
	}
}
void updatemin(vector<int>& FT,int idx,int amt){
	while(idx < FT.size()){
		FT[idx] = min(FT[idx],amt);
		idx += idx & -idx;
	}
}
void updatemax(vector<int>& FT,int idx,int amt){
	while(idx < FT.size()){
		FT[idx] = max(FT[idx],amt);
		idx += idx & -idx;
	}
}
void update(int c,int idx,int val){
	if(lb[c] == rb[c]){
		//cmpsegT[c][1] = val;
		updatemin(cmpsegTmn[c],1,val);
		updatemax(cmpsegTmx[c],1,val);
		return;
	}
	int k = (lb[c] + rb[c])/2;
	if(idx <= k){
		update(2*c,idx,val);
	}else{
		update(2*c+1,idx,val);
	}
	idx = lower_bound(cmpsegT[c].begin(),cmpsegT[c].end(),pts[idx].first) - cmpsegT[c].begin();
	updatemin(cmpsegTmn[c],idx,val);
	updatemax(cmpsegTmx[c],idx,val);
}
int query(int c,int l,int r){
	if(lb[c] == l && rb[c] == r) return segT[c];
	int k = (lb[c] + rb[c])/2;
	if(l <= k && k < r) return min(query(2*c,l,k),query(2*c+1,k+1,r));
	else if(r <= k) return query(2*c,l,r);
	else return query(2*c+1,l,r);
}
int qmin(vector<int>& FT,int idx){
	int mn = 1e9;
	while(idx > 0){
		mn = min(mn,FT[idx]);
		idx -= idx & -idx;
	}
	return mn;
}
int qmax(vector<int>& FT,int idx){
	int mx = -1;
	while(idx > 0){
		mx = max(mx,FT[idx]);
		idx -= idx & -idx;
	}
	return mx;
}
int getmin(int c,int l,int r,int x){
	if(lb[c] == l && rb[c] == r) return qmin(cmpsegTmn[c],lower_bound(cmpsegT[c].begin(),cmpsegT[c].end(),x)-cmpsegT[c].begin()-1);
	int k = (lb[c] + rb[c])/2;
	if(l <= k && k < r) return min(getmin(2*c,l,k,x),getmin(2*c+1,k+1,r,x));
	else if(r <= k) return getmin(2*c,l,r,x);
	else return getmin(2*c+1,l,r,x);
}
int getmax(int c,int l,int r,int x){
	if(lb[c] == l && rb[c] == r) return qmax(cmpsegTmx[c],lower_bound(cmpsegT[c].begin(),cmpsegT[c].end(),x)-cmpsegT[c].begin()-1);
	int k = (lb[c] + rb[c])/2;
	if(l <= k && k < r) return max(getmax(2*c,l,k,x),getmax(2*c+1,k+1,r,x));
	else if(r <= k) return getmax(2*c,l,r,x);
	else return getmax(2*c+1,l,r,x);
}
int main(){
	int n;
	scanf("%d",&n);
	int a,b;
	for(int i = 0; i < n; i++){
		scanf("%d%d",&a,&b);
		pts.emplace_back(a,b);
	}
	sort(pts.begin(),pts.end(),[](pair<int,int> x,pair<int,int> y){
		return x.second < y.second;
	});
	build(1,0,pts.size());
	int c = 0;
	for(int i = 0; i < n; i++){
		int idx = upper_bound(pts.begin(),pts.end(),make_pair(0,pts[i].first),[](pair<int,int> x,pair<int,int> y){
			return x.second < y.second;
		}) - pts.begin();
		bool ok = false;
		if(idx <= i-1 && query(1,idx,i-1) < pts[i].first){
			ok = true;
			if(getmin(1,idx,i-1,pts[i].first) != getmax(1,idx,i-1,pts[i].first)){
				printf("0\n");
				return 0;
			}else{
				update(1,i,!getmin(1,idx,i-1,pts[i].first));
			}
		}
		if(!ok){
			c++;
			update(1,i,0);
		}
	}
	int ans = 1;
	for(int i = 0; i < c; i++){
		ans *= 2;
		ans %= 1000000007;
	}
	printf("%d\n",ans);
	return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'void build(int, int, int)':
port_facility.cpp:45:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(ll < cmpsegT[2*c].size() && rr < cmpsegT[2*c+1].size()){
        ~~~^~~~~~~~~~~~~~~~~~~~~
port_facility.cpp:45:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(ll < cmpsegT[2*c].size() && rr < cmpsegT[2*c+1].size()){
                                    ~~~^~~~~~~~~~~~~~~~~~~~~~~
port_facility.cpp:58:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(ll < cmpsegT[2*c].size()){
        ~~~^~~~~~~~~~~~~~~~~~~~~
port_facility.cpp:64:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(rr < cmpsegT[2*c+1].size()){
        ~~~^~~~~~~~~~~~~~~~~~~~~~~
port_facility.cpp: In function 'void updatemin(std::vector<int>&, int, int)':
port_facility.cpp:72:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(idx < FT.size()){
        ~~~~^~~~~~~~~~~
port_facility.cpp: In function 'void updatemax(std::vector<int>&, int, int)':
port_facility.cpp:78:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(idx < FT.size()){
        ~~~~^~~~~~~~~~~
port_facility.cpp: In function 'int main()':
port_facility.cpp:139:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
port_facility.cpp:142:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b);
   ~~~~~^~~~~~~~~~~~~~

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