Submission #535682

#	Time	Username	Problem	Language	Result	Execution time	Memory
535682		Antekb	Port Facility (JOI17_port_facility)	C++14	0 / 100	91 ms	197284 KiB

port_facility

#include<bits/stdc++.h>
using namespace std;
#define st first
#define nd second
typedef pair<int, int> pii;
const int N=1<<21;
bool czy=1;
pii seg[N];
vector<int> tab[N+N], tab2[N+N];
void insert(int id){
	int l=seg[id].st+N, r=seg[id].nd+1+N;
	for(;l<r; l>>=1, r>>=1){
		if(l&1)tab[l++].push_back(id);
		if(r&1)tab[--r].push_back(id);
	}
}
void insert2(int id){
	int l=seg[id].st+N, r=seg[id].nd+1+N;
	for(;l<r; l>>=1, r>>=1){
		if(l&1)tab2[l++].push_back(id);
		if(r&1)tab2[--r].push_back(id);
	}
}

int vis[N];
void dfs(int s){
	vector<int> V;
	V.push_back(s);
	vis[s]=1;
	for(int i=0; i<V.size(); i++){
		int v=V[i];
		int l=seg[v].st+N, r=seg[v].nd+N;
		while(l){
			while(tab[l].size()){
				int u=tab[l].back();
				if(seg[u].nd>seg[v].nd)break;
				if(!vis[u]){
					vis[u]=3-vis[v];
					V.push_back(u);
				}
				tab[l].pop_back();
			}
			l/=2;
		}
		while(r){
			while(tab2[r].size()){
				int u=tab2[r].back();
				if(seg[u].st<seg[v].st)break;
				if(!vis[u]){
					vis[u]=3-vis[v];
					V.push_back(u);
				}
				tab2[r].pop_back();
			}
			r/=2;
		}
	}
}
bool solve(vector<int> id){
	vector<pair<int, pii> > V;
	for(int i:id){
		V.push_back({seg[i].st, {1, i}});
		V.push_back({seg[i].nd, {-1, i}});
	}
	vector<int> V2;
	sort(V.begin(), V.end());
	for(int i=0; i<V.size(); i++){
		if(V[i].nd.st==1)V2.push_back(V[i].nd.nd);
		else{
			if(!V2.size())return 0;
			if(V2.back()!=V[i].nd.nd)return 0;
			V2.pop_back();
		}
	}
	return 1;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;
	cin>>n;
	vector<pii> V3;
	for(int i=0; i<n; i++){
		cin>>seg[i].st>>seg[i].nd;
		//insert(i);
		V3.push_back({seg[i].st, i});
	}
	sort(V3.begin(), V3.end());
	for(int i=0; i<n; i++)insert2(i);
	V3.clear();
	for(int i=0; i<n; i++){
		V3.push_back({-seg[i].nd, i});
	}
	sort(V3.begin(), V3.end());
	for(int i=0; i<n; i++)insert(i);
	/*for(int i=1; i<N+N; i++){
		sort(tab[i].begin(), tab[i].end(), [](int a, int b){return seg[a].nd>seg[b].nd;});
		tab2[i]=tab[i];
		sort(tab2[i].begin(), tab2[i].end(), [](int a, int b){return seg[a].st<seg[b].st;});
	}*/
	int ile=0, ans=1;
	int mod=1e9+7;
	for(int i=0; i<n; i++){
		int j=i;
		if(!vis[j]){
			ile++;
			ans*=2;
			if(ans>=mod)ans-=mod;
			dfs(j);
		}
	}
	vector<int> V, V2;
	for(int i=0; i<n; i++){
		if(vis[i]==2)V.push_back(i);
		else V2.push_back(i);
	}
	czy=(solve(V)&solve(V2));
	if(!czy)ans=0;
	cout<<ans*czy;
}

Compilation message (stderr)

port_facility.cpp: In function 'void dfs(int)':
port_facility.cpp:30:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~
port_facility.cpp: In function 'bool solve(std::vector<int>)':
port_facility.cpp:67:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~

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