Submission #10376214


Source Code Expand

Copy
#include <bits/stdc++.h>
#define all(v) v.begin(),v.end()
#define eb emplace_back
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
inline void chmin(int& a,int b){a=min(a,b);}
const ll mod=1e9+7;
vector<int> dat[1<<22];
vector<P> G[1<<20];
int col[1<<20],vis[1<<20],dat2[1<<22],par[1<<20],sz[1<<20];
P v[1<<20];
struct UF{
	int n;
	void build(int n_){
		n=n_;
		for(int i=0;i<n;i++){
			par[i]=i;
			sz[i]=1;
		}
	}
	int root(int x){
		if(x==par[x])return x;
		return par[x]=root(par[x]);
	}
	bool unite(int u,int v){
		u=root(u),v=root(v);
		if(u==v)return false;
		if(sz[u]<sz[v])swap(u,v);
		sz[u]+=sz[v];
		par[v]=u;
		return true;
	}
}uf;
struct segtree{
	int n;
	segtree(int n_){
		n=1;
		while(n<n_)n<<=1;
		for(int i=0;i<2*n;i++)dat2[i]=-1;
	}
	void add(int k,int x){
		k+=n;
		dat[k].eb(x);
		k>>=1;
		while(k>0){
			dat[k].eb(x);
			k>>=1;
		}
	}
	void upd(int a,int b,int x,int k,int l,int r){
		if(b<=l||r<=a)return;
		if(a<=l&&r<=b){
			for(auto &e:dat[k]){
				if(uf.unite(x,e)){
					G[x].eb(e,1);
					G[e].eb(x,1);
				}
			}
			if(dat2[k]!=-1){
				if(uf.unite(x,dat2[k])){
					G[x].eb(dat2[k],0);
					G[dat2[k]].eb(x,0);
				}
			}else if(!dat[k].empty()){
				dat2[k]=x;
			}
			dat[k].clear();
			return;
		}
		int m=(l+r)>>1;
		upd(a,b,x,k<<1,l,m);
		upd(a,b,x,k<<1|1,m,r);
	}
};
ll mpow(ll x,ll n){
	ll res=1;
	while(n>0){
		if(n&1){
			res*=x;
			res%=mod;
		}
		x=x*x%mod;
		n>>=1;
	}
	return res;
}
void dfs(int i){
	vis[i]=1;
	for(auto &e:G[i]){
		if(vis[e.first])continue;
		col[e.first]=(col[i]^e.second);
		dfs(e.first);
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;cin>>n;
	uf.build(n);
	for(int i=0;i<n;i++){
		cin>>v[i].first>>v[i].second;
	}
	sort(v,v+n);
	segtree seg(2*n+1);
	stack<int> st[2];
	for(int i=0;i<n;i++){
		int l=v[i].first,r=v[i].second;
		seg.upd(l,r+1,i,1,0,seg.n);
		seg.add(r,i);
	}
	int co=0;
	for(int i=0;i<n;i++){
		if(!vis[i]){
			dfs(i);
			co++;
		}
	}
	for(int i=0;i<n;i++){
		int l=v[i].first,r=v[i].second;
		while(!st[col[i]].empty()&&st[col[i]].top()<l){
			st[col[i]].pop();
		}
		if(!st[col[i]].empty()&&st[col[i]].top()<r){
			cout<<0<<'\n';
			return 0;
		}
		st[col[i]].push(r);
	}
	cout<<mpow(2LL,co)<<'\n';
}

Submission Info

Submission Time
Task B - 港湾設備 (Port Facility)
User TAISA_
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2344 Byte
Status
Exec Time 3166 ms
Memory 410828 KB

Judge Result

Set Name Score / Max Score Test Cases
Subtask01 10 / 10 sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt
Subtask02 12 / 12 sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt, 02-17.txt, 02-18.txt, 02-19.txt, 02-20.txt
Subtask03 56 / 56 sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt, 02-17.txt, 02-18.txt, 02-19.txt, 02-20.txt, 03-01.txt, 03-02.txt, 03-03.txt, 03-04.txt, 03-05.txt, 03-06.txt, 03-07.txt, 03-08.txt, 03-09.txt, 03-10.txt, 03-11.txt, 03-12.txt, 03-13.txt, 03-14.txt, 03-15.txt, 03-16.txt, 03-17.txt, 03-18.txt, 03-19.txt, 03-20.txt, 03-21.txt, 03-22.txt, 03-23.txt, 03-24.txt, 03-25.txt, 03-26.txt, 03-27.txt, 03-28.txt, 03-29.txt, 03-30.txt, 03-31.txt, 03-32.txt, 03-33.txt, 03-34.txt, 03-35.txt
Subtask04 22 / 22 sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt, 02-17.txt, 02-18.txt, 02-19.txt, 02-20.txt, 03-01.txt, 03-02.txt, 03-03.txt, 03-04.txt, 03-05.txt, 03-06.txt, 03-07.txt, 03-08.txt, 03-09.txt, 03-10.txt, 03-11.txt, 03-12.txt, 03-13.txt, 03-14.txt, 03-15.txt, 03-16.txt, 03-17.txt, 03-18.txt, 03-19.txt, 03-20.txt, 03-21.txt, 03-22.txt, 03-23.txt, 03-24.txt, 03-25.txt, 03-26.txt, 03-27.txt, 03-28.txt, 03-29.txt, 03-30.txt, 03-31.txt, 03-32.txt, 03-33.txt, 03-34.txt, 03-35.txt, 04-01.txt, 04-02.txt, 04-03.txt, 04-04.txt, 04-05.txt, 04-06.txt, 04-07.txt, 04-08.txt, 04-09.txt, 04-10.txt, 04-11.txt, 04-12.txt, 04-13.txt, 04-14.txt, 04-15.txt, 04-16.txt, 04-17.txt, 04-18.txt, 04-19.txt, 04-20.txt, 04-21.txt, 04-22.txt, 04-23.txt, 04-24.txt, 04-25.txt, 04-26.txt, 04-27.txt, 04-28.txt, 04-29.txt, 04-30.txt, 04-31.txt, 04-32.txt, 04-33.txt, 04-34.txt, 04-35.txt
Case Name Status Exec Time Memory
01-01.txt 42 ms 133376 KB
01-02.txt 42 ms 133376 KB
01-03.txt 42 ms 133376 KB
01-04.txt 42 ms 133376 KB
01-05.txt 42 ms 133376 KB
01-06.txt 42 ms 133376 KB
01-07.txt 42 ms 133376 KB
01-08.txt 42 ms 133376 KB
01-09.txt 42 ms 133376 KB
01-10.txt 43 ms 133376 KB
01-11.txt 43 ms 133376 KB
01-12.txt 42 ms 133376 KB
01-13.txt 42 ms 133376 KB
01-14.txt 42 ms 131328 KB
01-15.txt 42 ms 131328 KB
01-16.txt 42 ms 133376 KB
01-17.txt 42 ms 133376 KB
01-18.txt 42 ms 133376 KB
01-19.txt 41 ms 131328 KB
01-20.txt 42 ms 133376 KB
01-21.txt 42 ms 131328 KB
01-22.txt 41 ms 131328 KB
01-23.txt 42 ms 133376 KB
01-24.txt 42 ms 133376 KB
02-01.txt 44 ms 133760 KB
02-02.txt 44 ms 133760 KB
02-03.txt 44 ms 133760 KB
02-04.txt 44 ms 133760 KB
02-05.txt 44 ms 133760 KB
02-06.txt 44 ms 133760 KB
02-07.txt 44 ms 133760 KB
02-08.txt 44 ms 133760 KB
02-09.txt 44 ms 133760 KB
02-10.txt 44 ms 133760 KB
02-11.txt 43 ms 131712 KB
02-12.txt 43 ms 131584 KB
02-13.txt 44 ms 133760 KB
02-14.txt 44 ms 133760 KB
02-15.txt 43 ms 133760 KB
02-16.txt 43 ms 131712 KB
02-17.txt 44 ms 133760 KB
02-18.txt 44 ms 133760 KB
02-19.txt 44 ms 133888 KB
02-20.txt 44 ms 133888 KB
03-01.txt 166 ms 155888 KB
03-02.txt 173 ms 155888 KB
03-03.txt 167 ms 155888 KB
03-04.txt 167 ms 155760 KB
03-05.txt 175 ms 155888 KB
03-06.txt 169 ms 155760 KB
03-07.txt 167 ms 155760 KB
03-08.txt 124 ms 149876 KB
03-09.txt 134 ms 147564 KB
03-10.txt 152 ms 153968 KB
03-11.txt 151 ms 153968 KB
03-12.txt 151 ms 153968 KB
03-13.txt 139 ms 154996 KB
03-14.txt 124 ms 149876 KB
03-15.txt 147 ms 153844 KB
03-16.txt 160 ms 155252 KB
03-17.txt 163 ms 156148 KB
03-18.txt 150 ms 154864 KB
03-19.txt 157 ms 155380 KB
03-20.txt 161 ms 156020 KB
03-21.txt 216 ms 153208 KB
03-22.txt 218 ms 153208 KB
03-23.txt 163 ms 156268 KB
03-24.txt 164 ms 156264 KB
03-25.txt 167 ms 156272 KB
03-26.txt 167 ms 156272 KB
03-27.txt 145 ms 154220 KB
03-28.txt 146 ms 154220 KB
03-29.txt 146 ms 154352 KB
03-30.txt 146 ms 154352 KB
03-31.txt 144 ms 159732 KB
03-32.txt 150 ms 159732 KB
03-33.txt 153 ms 159732 KB
03-34.txt 166 ms 155888 KB
03-35.txt 166 ms 155888 KB
04-01.txt 1607 ms 373560 KB
04-02.txt 1620 ms 372920 KB
04-03.txt 1597 ms 373304 KB
04-04.txt 1619 ms 373176 KB
04-05.txt 1620 ms 373816 KB
04-06.txt 1579 ms 371384 KB
04-07.txt 1584 ms 373304 KB
04-08.txt 1060 ms 328780 KB
04-09.txt 1164 ms 305468 KB
04-10.txt 1376 ms 353108 KB
04-11.txt 1370 ms 353124 KB
04-12.txt 1368 ms 352740 KB
04-13.txt 1243 ms 364108 KB
04-14.txt 1056 ms 328652 KB
04-15.txt 1456 ms 357576 KB
04-16.txt 1569 ms 374584 KB
04-17.txt 1548 ms 376520 KB
04-18.txt 1442 ms 362948 KB
04-19.txt 1535 ms 373576 KB
04-20.txt 1512 ms 373832 KB
04-21.txt 3166 ms 340588 KB
04-22.txt 3130 ms 339820 KB
04-23.txt 1551 ms 377404 KB
04-24.txt 1548 ms 377532 KB
04-25.txt 1570 ms 378052 KB
04-26.txt 1574 ms 377028 KB
04-27.txt 1293 ms 356276 KB
04-28.txt 1290 ms 356276 KB
04-29.txt 1311 ms 355380 KB
04-30.txt 1310 ms 355380 KB
04-31.txt 1319 ms 410828 KB
04-32.txt 1379 ms 410696 KB
04-33.txt 1380 ms 410696 KB
04-34.txt 1608 ms 373560 KB
04-35.txt 1619 ms 372920 KB
sample-01.txt 42 ms 133376 KB
sample-02.txt 42 ms 133376 KB
sample-03.txt 42 ms 133376 KB
sample-04.txt 42 ms 133376 KB