Submission #720271

#	Time	Username	Problem	Language	Result	Execution time	Memory
720271		NothingXD	Port Facility (JOI17_port_facility)	C++17	100 / 100	1917 ms	166776 KiB

port_facility

/*

   Wei Wai Wei Wai
   Zumigat nan damu dimi kwayt rayt

*/

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;
/*typedef __uint128_t L;
  struct FastMod {
  ull b, m;
  FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
  ull reduce(ull a) {
  ull q = (ull)((L(m) * a) >> 64);
  ull r = a - q * b; // can be proven that 0 <= r < 2*b
  return r >= b ? r - b : r;
  }
  };
  FastMod FM(2);
*/
void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2e6 + 10;
const int inf = 1e9;
const int mod = 1e9 + 7;
int n, a[maxn];
pair<pii,pii> seg[maxn << 2];
vector<pii> ver[maxn];

pair<pii,pii> operator +(pair<pii,pii> a, pair<pii,pii> b){
	return MP(min(a.F, b.F), max(a.S, b.S));
}

void build(int v, int l, int r){
	if (l + 1 == r){
		seg[v] = {{a[l], l}, {a[l], l}};
		return;
	}
	int mid = (l + r) >> 1;
	build(v << 1, l, mid);
	build(v << 1 |1, mid, r);
	seg[v] = seg[v << 1] + seg[v << 1 | 1];
}

void change(int v, int l, int r, int idx){
	if (idx < l || r <= idx) return;
	if (l + 1 == r){
		seg[v] = {{idx, idx}, {idx, idx}};
		return;
	}
	int mid = (l + r) >> 1;
	change(v << 1, l, mid, idx);
	change(v << 1 | 1, mid, r, idx);
	seg[v] = seg[v << 1] + seg[v << 1 | 1];
}

pair<pii,pii> get(int v, int l, int r, int ql, int qr){
	if (qr <= l || r <= ql) return {{inf, inf}, {0, 0}};
	if (ql <= l && r <= qr) return seg[v];
	int mid = (l + r) >> 1;
	return get(v << 1, l, mid, ql, qr)
		+ get(v << 1 | 1, mid, r, ql, qr);
}

void bfs(pii st){
	change(1, 1, 2*n+1, st.F);
	change(1, 1, 2*n+1, st.S);
	ver[0].push_back(st);
	for (int i = 0; i < n; i++){
		if (ver[i].empty()) break;
		vector<int> tmp, val;
		for (auto [x, y]: ver[i]){
			tmp.push_back(x);
			tmp.push_back(y);
		}
		sort(all(tmp));
		for (auto x: tmp){
			if (a[x] > x) val.push_back(x);
			else if (val.empty() || val.back() != a[x]){
				cout << "0\n";
				exit(0);
			}
			else val.pop_back();
		}
		for (auto x: ver[i]){
			pair<pii,pii> tmp = get(1, 1, 2*n+1, x.F, x.S + 1);
			while(tmp.F.F < x.F || tmp.S.F > x.S){
				if (tmp.F.F < x.F){
					ver[i+1].push_back(tmp.F);
					change(1, 1, 2*n+1, tmp.F.F);
					change(1, 1, 2*n+1, tmp.F.S);
				}
				if (tmp.S.F > x.S){
					ver[i+1].push_back({tmp.S.S, tmp.S.F});
					change(1, 1, 2*n+1, tmp.S.F);
					change(1, 1, 2*n+1, tmp.S.S);
				}
				tmp = get(1, 1, 2*n+1, x.F, x.S+1);
			}
		}
		ver[i].clear();
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	cin >> n;
	for (int i = 1; i <= n; i++){
		int l, r; cin >> l >> r;
		a[l] = r;
		a[r] = l;
	}

	build(1, 1, 2*n+1);

	int ans = 1;

	for (int i = 1; i <= 2*n; i++){
		pair<pii,pii> tmp = get(1, 1, 2*n+1, i, i+1);
		if (tmp.F.F != i){
			ans = 2 * ans % mod;
			bfs({min(tmp.F.F, tmp.F.S), max(tmp.F.F, tmp.F.S)});
		}
	}

	cout << ans << '\n';

	return 0;
}

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