Submission #79483

#	Time	Username	Problem	Language	Result	Execution time	Memory
79483		Plurm	Port Facility (JOI17_port_facility)	C++11	0 / 100	24 ms	23800 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<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;
		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 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 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 = lower_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();
		if(idx <= i-1 && query(1,idx,i-1) < pts[i].first){
			;
		}else{
			c++;
		}
	}
	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 'int main()':
port_facility.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
port_facility.cpp:44: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