Submission #995342

#	Time	Username	Problem	Language	Result	Execution time	Memory
995342		jcelin	Port Facility (JOI17_port_facility)	C++14	100 / 100	2031 ms	411040 KiB

port_facility

#include<bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define PB push_back
#define PPB pop_back
#define all(x) (x).begin(), (x).end()

typedef vector<int> vi; 
typedef pair<int, int> ii;
typedef vector<ii> vii;

const int MAXN = 2e6 + 7;
const int logo = 21;
const int off = 1 << logo;
const int trsz = off << 1;
const int mod = 1e9 + 7;

int L[MAXN], R[MAXN], rev[MAXN], bio[MAXN];
vi g[MAXN], vec[MAXN];
vii ev;
set<ii> act;

struct fin{
	set<int> p[MAXN];
	int sz[MAXN], par[MAXN], ud[MAXN];
	
	void init(){
		for(int i=0; i<MAXN; i++) par[i] = i, sz[i] = 1, ud[i] = 0, p[i].insert(L[i]);
	}
	
	int find(int x){
		return x == par[x] ? x : find(par[x]);
	}
	
	int dis(int x){
		if(x == par[x]) return 0;
		return ud[x] ^ dis(par[x]);
	}
	
	void merge(int a, int b){
		int da = dis(a), db = dis(b);
		a = find(a), b = find(b);
		if(sz[a] < sz[b]) swap(a, b);
		
		for(auto &x : p[b]) p[a].insert(x);
		p[b].clear();
		da ^= db ^ 1;
		ud[b] = da;
		sz[a] += sz[b];
		par[b] = a;
	}
	
	void ubaci(int id){
		id = find(id);
		if(p[id].empty()) return;
		act.insert({*(--p[id].end()), id});
	}
	
	void izbaci(int id){
		id = find(id);
		if(p[id].empty()) return;
		act.erase({*(--p[id].end()), id});
	}
	
	void brisi(int id, int vl){
		id = find(id);
		p[id].erase(vl);
	}
	
}uf;

struct tournament{
	int seg[trsz];
	
	void update(int x, int vl){
		x += off;
		seg[x] = vl;
		for(x /= 2; x; x /= 2) seg[x] = max(seg[x * 2], seg[x * 2 + 1]); 
	}
	
	int query(int l, int r){
		int ret = 0;
		for(l += off, r += off; l < r; l >>= 1, r >>= 1){
			if(l & 1) ret = max(ret, seg[l++]);
			if(r & 1) ret = max(ret, seg[--r]);
		}
		return ret;
	}
}t[3];


void add_edge(int a, int b){
	g[a].PB(b);
	g[b].PB(a);
}


void solve(){
	int n;
	cin >> n;
	for(int i=1; i<=n; i++){
		cin >> L[i] >> R[i];
		rev[L[i]] = i;
		ev.PB({L[i], i});
		ev.PB({R[i], -i});
	}
	sort(all(ev));
	uf.init();
	
	for(auto &x : ev){
		int id = abs(x.Y);
		if(x.Y > 0) uf.ubaci(id);
		else{
			uf.izbaci(id);
			uf.brisi(id, L[id]);
			
			vi unit;
			while(1){
				auto it = act.end();
				if(it == act.begin()) break;
				it--;
				if(it -> X < L[id]) break;
				unit.PB(it -> X);
				act.erase(it);
			}
			for(auto &y : unit) uf.merge(id, rev[y]);
			uf.ubaci(id);
			
			
		}
	
	}
	
	for(int i=1; i<=n; i++) vec[uf.find(i)].PB(i), bio[i] = uf.dis(i);
	
	int cnt = 0;
	for(int i=1; i<=n; i++){
		if(vec[i].empty()) continue;
		cnt++;
		for(auto &x : vec[i]) t[bio[x]].update(L[x], R[x]);
		for(auto &x : vec[i]){
			if(t[bio[x]].query(L[x], R[x] + 1) > R[x]){
				cout << 0 << "\n";
				return;
			}
		}
		for(auto &x : vec[i]) t[bio[x]].update(L[x], 0);
	}
	int ans = 1;
	for(int i=0; i<cnt; i++) ans *= 2, ans %= mod;
	cout << ans << "\n";
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int tt = 1;
	//cin >> t;
	while(tt--) solve();
	return 0;
}

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