Submission #79508

#	Time	Username	Problem	Language	Result	Execution time	Memory
79508		Plurm	Port Facility (JOI17_port_facility)	C++11	0 / 100	8 ms	6136 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
int segT[4*20005];
int lb[4*20005];
int rb[4*20005];
vector<int> cmpsegT[4*20005];
vector<int> cmpsegTmn[4*20005];
vector<int> cmpsegTmx[4*20005];
vector<pair<int,int> > pts;
int p[20005];
int bck[2*20005];
int fn(int x){
	if(p[x] == -1) return x;
	else return p[x] = fn(p[x]);
}
void un(int x,int y){
	x = fn(x);
	y = fn(y);
	if(x != y) p[x] = y;
}
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]){
		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);
}
void updatelink(int c,int l,int r,int lim,int lnk){
	if(lb[c] == l && rb[c] == r){
		for(int i = 1; i < cmpsegT[c].size(); i++){
			if(cmpsegT[c][i] < lim){
				un(bck[cmpsegT[c][i]],lnk);
			}else{
				break;
			}
		}
		return;
	}
	int k = (lb[c] + rb[c])/2;
	if(l <= k && k < r){
		updatelink(2*c,l,k,lim,lnk);
		updatelink(2*c+1,k+1,r,lim,lnk);
	}else if(r <= k){
		updatelink(2*c,l,r,lim,lnk);
	}else{
		updatelink(2*c+1,l,r,lim,lnk);
	}
}
int main(){
	memset(p,-1,sizeof(p));
	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;
	});
	for(int i = 0; i < n; i++){
		bck[pts[i].first] = i;
	}
	build(1,0,pts.size()-1);
	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));
				updatelink(1,idx,i-1,pts[i].first,i);
			}
		}
		if(!ok){
			update(1,i,0);
		}
	}
	set<int> s;
	for(int i = 0; i < n; i++){
		s.insert(fn(i));
	}
	c = s.size();
	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:43: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:43: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:56:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(ll < cmpsegT[2*c].size()){
        ~~~^~~~~~~~~~~~~~~~~~~~~
port_facility.cpp:62: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:70: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:76:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(idx < FT.size()){
        ~~~~^~~~~~~~~~~
port_facility.cpp: In function 'void updatelink(int, int, int, int, int)':
port_facility.cpp:136:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < cmpsegT[c].size(); i++){
                  ~~^~~~~~~~~~~~~~~~~~~
port_facility.cpp: In function 'int main()':
port_facility.cpp:158:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
port_facility.cpp:161: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