Submission #406896

#	Time	Username	Problem	Language	Result	Execution time	Memory
406896		ritul_kr_singh	Port Facility (JOI17_port_facility)	C++17	100 / 100	3876 ms	422700 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

const int MOD = 1e9+7, MAXN = 1e6, INF = 1e18;

struct SegmentTree{
	using T = array<int, 2>;
	vector<T> a; int sz = 1; T ID = {-INF, -1};
	void init(vector<T> &v){
		while(sz < (int)v.size()) sz += sz;
		a.assign(2*sz, ID);
		build(v, 0, 0, sz);
	}
	void build(vector<T> &v, int x, int lx, int rx){
		if(rx-lx==1){
			if(lx < (int)v.size()) a[x] = v[lx];
			return;
		}
		int mx = (lx + rx) / 2;
		build(v, 2*x+1, lx, mx);
		build(v, 2*x+2, mx, rx);
		a[x] = max(a[2*x+1], a[2*x+2]);
	}
	void update(int i, int x, int lx, int rx){
		if(rx-lx==1) return void(a[x] = ID);
		int mx = (lx + rx) / 2;
		if(i < mx) update(i, 2*x+1, lx, mx);
		else update(i, 2*x+2, mx, rx);
		a[x] = max(a[2*x+1], a[2*x+2]);
	}
	void update(int i){ update(i, 0, 0, sz); }
	T rangeMax(int l, int r, int x, int lx, int rx){
		if(r<=lx || rx<=l) return ID;
		if(l<=lx && rx<=r) return a[x];
		int mx = (lx + rx) / 2;
		return max(rangeMax(l, r, 2*x+1, lx, mx), rangeMax(l, r, 2*x+2, mx, rx));
	}
	T rangeMax(int l, int r){ return rangeMax(l, r+1, 0, 0, sz); }
} st0, st1;

bitset<MAXN> vis, c;
int a[MAXN], b[MAXN];

void dfs(int u){
	int v;
	vis[u] = 1;
	st0.update(a[u]);
	st1.update(b[u]);
	while((v = st0.rangeMax(a[u], b[u])[1]) >= 0){
		if(b[v] < b[u]) break;
		c[v] = c[u] ^ 1;
		dfs(v);
	}
	while((v = st1.rangeMax(a[u], b[u])[1]) >= 0){
		if(a[v] > a[u]) break;
		c[v] = c[u] ^ 1;
		dfs(v);
	}
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	
	int n; cin >> n;
	int s[n+n];
	vector<array<int, 2>> v0(n+n, {-INF, -1}), v1(n+n, {-INF, -1});
	for(int i=0; i<n; ++i){
		cin >> a[i] >> b[i]; --a[i], --b[i];
		s[a[i]] = s[b[i]] = i;
		v0[a[i]] = {b[i], i};
		v1[b[i]] = {-a[i], i};
	}

	st0.init(v0), st1.init(v1);

	int cnt = 1;

	for(int i=0; i<n; ++i){
		if(vis[i]) continue;
		cnt = (cnt + cnt) % MOD;
		dfs(i);
	}

	vector<int> curr[2];

	for(int i=0; i<n+n; ++i){
		int j = s[i];
		if(a[j] == i){
			curr[c[j]].push_back(j);
		}else{
			if(curr[c[j]].back() != j){
				cout << 0;
				return 0;
			}else curr[c[j]].pop_back();
		}
	}

	cout << cnt;
}

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