제출 #1225015

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1225015		emptypringlescan	Port Facility (JOI17_port_facility)	C++17	100 / 100	427 ms	125628 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
bool cmp(pair<int,int> a,pair<int,int> b){
	return a.second<b.second;
}
int fenw[2000005];
void update(int x, int v){
	for(;x<2000005; x+=x&-x) fenw[x]+=v;
}
int query(int x){
	int ret=0;
	for(;x;x-=x&-x) ret+=fenw[x];
	return ret;
}
vector<pair<int,int> > adj[1000005];
bool can=true;
int col[1000005];
void dfs(int x, int c){
	assert(col[x]==-1);
	col[x]=c;
	for(auto i:adj[x]){
		if(col[i.first]==-1) dfs(i.first,c^i.second);
		else{
			if(col[i.first]!=(c^i.second)) can=false;
		}
	}
}
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	pair<int,int> arr[n];
	for(int i=0; i<n; i++) cin >> arr[i].first >> arr[i].second;
	sort(arr,arr+n,cmp);
	for(int i=1; i<=2*n; i++) update(i,1);
	vector<int> mono;
	for(int i=0; i<n; i++){
		update(arr[i].first,-1);
		update(arr[i].second,-1);
		while(!mono.empty()&&arr[mono.back()].first>arr[i].first){
			int x=mono.back();
			mono.pop_back();
			if(query(arr[x].second)-query(arr[x].first-1)){
				adj[x].push_back({i,0});
				adj[i].push_back({x,0});
			}
		}
		if(!mono.empty()&&arr[mono.back()].second>arr[i].first){
			int x=mono.back();
			if(query(arr[x].second)-query(arr[i].first-1)){
				cout << 0;
				return 0;
			}
			adj[x].push_back({i,1});
			adj[i].push_back({x,1});
		}
		mono.push_back(i);
	}
	memset(col,-1,sizeof(col));
	int con=0;
	for(int i=0; i<n; i++) if(col[i]==-1){
		dfs(i,0);
		con++;
	}
	if(!can){
		cout << 0;
		return 0;
	}
	long long ans=1;
	for(int i=0; i<con; i++){
		ans*=2ll;
		ans%=1000000007;
	}
	cout << ans;
}

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