Submission #136947

#	Time	Username	Problem	Language	Result	Execution time	Memory
136947		dndhk	Port Facility (JOI17_port_facility)	C++14	0 / 100	3 ms	376 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;

struct UNIONFIND{
	int SZ;
	vector<int> group;
	void init(int x){
		SZ = x;
		for(int i=0; i<=SZ; i++){
			group.pb(i);
		}
	}
	int find_g(int x){
		return x==group[x] ? x : group[x] = find_g(group[x]);
	}
	void union_g(int x, int y){
		x = find_g(x); y = find_g(y);
		group[x] = y;
	}
	int calc_num(){
		int ret = 0;
		for(int i=1; i<=SZ; i++){
			if(find_g(i)==i)	ret++;
		}
		return ret;
	}
};

UNIONFIND UF;

bool simul(){
	int idx = 0;
	deque<int> dq1, dq2;
	for(int i=1; i<=2*N; i++){
		if(idx<N && vt[idx].first==i){
			int add = vt[idx++].second;
			if(dq1.empty()){
				dq1.pb(add);
				continue;
			}else if(dq2.empty()){
				if(add>dq1.back()){
					dq2.pb(add);
				}else{
					dq1.pb(add);
				}
			}else{
				int b1 = dq1.back(); int b2 = dq2.back();
				if(add<b1 && add<b2){
					if(b1<b2)	dq1.pb(add);
					else	dq2.pb(add);
				}else if(add<b1){
					dq1.pb(add); continue;
				}else if(add<b2){
					dq2.pb(add); continue;
				}else{
					return false;
				}
			}
		}else{
			if(!dq1.empty() && dq1.back()==i)	dq1.pop_back();
			else if(!dq2.empty() && dq2.back()==i)	dq2.pop_back();
			else	return false;
		}
	}
	return true;
}

struct SEG{
	struct NODE{
		int l=-1, r=-1;
		map<int, int> mp;
		bool lazy = false;
	};
	vector<NODE> seg;
	int SZ, cnt;
	void Init(int x){
		SZ = x; seg.resize(SZ*2);
		cnt = 1;
		init(0, 1, SZ);
	}
	void chk2(int idx){
		int cnt = 0;
		if(seg[idx].mp.empty())	return;
		int k;
		for(map<int, int>::iterator it = seg[idx].mp.begin(); it!=seg[idx].mp.end(); it++){
			k = it->first;
			cnt+=it->second;
		}
		seg[idx].mp.clear();
		seg[idx].mp[UF.find_g(k)] = cnt;
		seg[idx].lazy = true;
	}
	void chk(int idx){
		if(seg[idx].lazy==false)	return;
		seg[idx].lazy = false;
		if(seg[idx].l==-1)	return;
		chk2(seg[idx].l);
		chk2(seg[idx].r);
	}
	void init(int idx, int s, int e){
		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, int y, int z){
		update(0, 1, SZ, x, y, z);
	}
	void update(int idx, int s, int e, int x, int y, int z){
		chk(idx);
		if(z==1)	{
			seg[idx].mp[y]++;
		}
		else{
			if(seg[idx].mp.find(y)==seg[idx].mp.end()){
				int k = UF.find_g(y);
				seg[idx].mp[k]--;
				if(seg[idx].mp[k]==0){
					seg[idx].mp.erase(k);
				}
			}else{
				seg[idx].mp[y]--;
				if(seg[idx].mp[y]==0){
					seg[idx].mp.erase(y);	
				}
			}
		}
		if(s==e)	return;
		if(x<=(s+e)/2){
			update(seg[idx].l, s, (s+e)/2, x, y, z);
		}else{
			update(seg[idx].r, (s+e)/2+1, e, x, y, z);
		}
	}
	void Calc(int x, int y, int z){
		calc(0, 1, SZ, x, y, z);
	}
	void calc(int idx, int s, int e, int x, int y, int z){
		chk(idx);
		if(x<=s && e<=y){
			int cnt = 0;
			//cout<<s<<" "<<e<<" "<<x<<" "<<y<<" "<<z<<endl;
			for(map<int, int>::iterator it = seg[idx].mp.begin(); it!=seg[idx].mp.end(); it++){
				//cout<<"*"<<z<<" "<<it->first<<endl;
				UF.union_g(z, it->first);
				cnt+=it->second;
			}
			seg[idx].mp.clear();
			if(cnt!=0)	{
				seg[idx].mp[UF.find_g(z)] = cnt;
				seg[idx].lazy = true;
			}
			return;
		}else if(x>e || y<s)	return;
		calc(seg[idx].l, s, (s+e)/2, x, y, z);
		calc(seg[idx].r, (s+e)/2+1, e, x, y, z);
	}
};

SEG Seg;

int num[MAX_N*2+1];

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());
	if(!simul()){
		printf("0");
		return 0;
	}
	int idx = 0;
	UF.init(N);
	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<<" "<<idx+1<<endl;
			Seg.Calc(vt[idx].first, vt[idx].second, idx+1);
			Seg.Update(vt[idx].second, idx+1, 1);
			num[vt[idx].second] = idx+1;
			idx++;
		}else{
			//cout<<i<<" "<<num[i]<<endl;
			Seg.Update(i, num[i], -1);
		}
	}
	int t = UF.calc_num();
	ll ans = 1;
	for(int i=1; i<=t; i++){
		ans = (ans*2)%DIV;
	}
	cout<<ans;
	return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:190:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
port_facility.cpp:193:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
port_facility.cpp: In member function 'void SEG::calc(int, int, int, int, int, int)':
port_facility.cpp:39:20: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   return x==group[x] ? x : group[x] = find_g(group[x]);
                    ^
port_facility.cpp:109:7: note: 'k' was declared here
   int k;
       ^
port_facility.cpp:39:20: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   return x==group[x] ? x : group[x] = find_g(group[x]);
                    ^
port_facility.cpp:109:7: note: 'k' was declared here
   int k;
       ^
port_facility.cpp: In member function 'void SEG::update(int, int, int, int, int, int)':
port_facility.cpp:39:20: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   return x==group[x] ? x : group[x] = find_g(group[x]);
                    ^
port_facility.cpp:109:7: note: 'k' was declared here
   int k;
       ^
port_facility.cpp:39:20: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   return x==group[x] ? x : group[x] = find_g(group[x]);
                    ^
port_facility.cpp:109:7: note: 'k' was declared here
   int k;
       ^
port_facility.cpp: In function 'int main()':
port_facility.cpp:39:20: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   return x==group[x] ? x : group[x] = find_g(group[x]);
                    ^
port_facility.cpp:109:7: note: 'k' was declared here
   int k;
       ^
port_facility.cpp:39:20: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   return x==group[x] ? x : group[x] = find_g(group[x]);
                    ^
port_facility.cpp:109:7: note: 'k' was declared here
   int k;
       ^

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