Submission #137576

#	Time	Username	Problem	Language	Result	Execution time	Memory
137576		Retro3014	Port Facility (JOI17_port_facility)	C++17	78 / 100	6098 ms	674364 KiB

port_facility

#include <bits/stdc++.h>
 
#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL
 
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const ll DIV = 1000000007;
const int MAX_N = 1000000;
int N;
vector<pii> vt;
 
bool zero = false;
vector<int> gp[MAX_N*2+1];
int c[MAX_N*2+1];
 
 
int t, k;
 
struct SEG{
	/*
	struct NODE{
		int l=-1, r=-1;
		vector<int> v;
		int sz=0;
	};
	vector<NODE> seg;
	int SZ, cnt;
	void Init(int x){
		SZ = x; seg.resize(SZ*2);
		cnt = 1;
		init(0, 1, SZ);
	}
	void init(int idx, int s, int e){
		//seg[idx].v.reserve(e-s+1);
		if(s==e)	return;
		seg[idx].l = cnt++; seg[idx].r = cnt++;
		init(seg[idx].l, s, (s+e)/2);
		init(seg[idx].r, (s+e)/2+1, e);
	}
	void Update(int x){
		update(0, 1, SZ, x);
	}
	void update(int idx, int s, int e, int k){
		//cout<<idx<<" "<<s<<" "<<e<<" "<<x<<" "<<y<<endl;
		seg[idx].v.pb(k);
		if(s==e)	return;
		if(k<=(s+e)/2){
			update(seg[idx].l, s, (s+e)/2, k);
		}else{
			update(seg[idx].r, (s+e)/2+1, e, k);
		}
	}
	void Calc(int x, int y){
		calc(0, 1, SZ, x, y);
	}
	void calc(int idx, int s, int e, int x, int y){
		if(seg[idx].v.empty())	return;
		//cout<<idx<<" "<<s<<" "<<e<<" "<<x<<" "<<y<<endl;
		if(x<=s && e<=y){
			k=0;
			//cout<<idx<<" "<<s<<" "<<e<<" "<<x<<" "<<y<<endl;
			while(!seg[idx].v.empty()){
				t = seg[idx].v.back(); seg[idx].v.pop_back();
				k = max(k, t);
				gp[t].pb(y); gp[y].pb(t);
			}
			if(k!=0)	seg[idx].v.pb(k);
			return;
		}else if(x>e || y<s)	return;
		calc(seg[idx].l, s, (s+e)/2, x, y);
		calc(seg[idx].r, (s+e)/2+1, e, x, y);
	}*/
	vector<int> seg[MAX_N*8];
	int two = 1;
	void Init(int sz){
		while(two<=sz)	two*=2;
	}
	void Update(int x){
		int idx = x + two;
		while(idx>0)	{
			seg[idx].pb(x);
			idx/=2;
		}
	}
	void Calc(int x, int y){
		int a = y;
		x+=two, y+=two;
		while(x<=y){
			if(x==y){
				calc(x, a);
				return;
			}
			if(x%2)	{
				calc(x, a);
				x++;
			}
			if(!(y%2)){
				calc(y, a);
				y--;
			}
			x/=2; y/=2;
		}
	}
	void calc(int x, int y){
		k = 0;
		while(!seg[x].empty()){
			gp[y].pb(seg[x].back()); gp[seg[x].back()].pb(y);
			k = max(seg[x].back(), k);
			seg[x].pop_back();
		}
		if(k!=0){
			seg[x].pb(k);
		}
	}
};
 
SEG Seg;
 
vector<int> dq;
 
void bfs(int x){
	dq.pb(x);
	while(!dq.empty()){
		x = dq.back(); dq.pop_back();
		for(int i : gp[x]){
			if(c[i]==0){
				c[i] = 3 - c[x];
				dq.pb(i);
			}else if(c[i]==c[x]){
				zero=true;
				return;
			}
		}
	}
}
 
vector<int> sc;
 
int main(){
	scanf("%d", &N);
	for(int i=1; i<=N; i++){
		int a, b;
		scanf("%d%d", &a, &b);
		vt.pb({a, b});
	}
	sort(vt.begin(), vt.end());
	int idx = 0;
	//UF.init(N*2);
	Seg.Init(N*2);
	for(int i=1; i<=N*2; i++){
		if(idx<N && vt[idx].first==i){
			//cout<<vt[idx].first<<" "<<vt[idx].second<<endl;
			Seg.Calc(vt[idx].first, vt[idx].second);
			Seg.Update(vt[idx].second);
			idx++;
		}else{
			sc.pb(i);
		}
	}
	ll ans = 1;
	//ll num=0;
	for(int i : sc){
		//num+=gp[i].size();
		if(c[i]==0){
			c[i] = 1;
			bfs(i);
			if(zero){
				printf("0");
				return 0;
			}
			ans = (ans*(ll)2)%DIV;
		}
	}
	//cout<<num<<endl;
	cout<<ans;
	return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:157:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
port_facility.cpp:160: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: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 56 / 56
• Subtask 4: 0 / 22