제출 #1275305

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275305		g4yuhg	Port Facility (JOI17_port_facility)	C++20	100 / 100	3212 ms	191196 KiB

port_facility

//Huyduocdithitp
#include <bits/stdc++.h>
typedef int ll;
#define pii pair<ll, ll>
#define MP make_pair
#define fi first
#define se second
#define TASK "flip3"
#define start if(fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);
#define N 2000006
#define LOG 19
#define endl '\n'
using namespace std;

const ll inf = 2e9, mod = 1e9 + 7;

bool ghuy4g;

ll n;
ll a[N], b[N];

pii st1[4 * N], st2[4 * N];

void upd1(ll id, ll l, ll r, ll i, pii v) {
	if (i > r || i < l) return;
	if (l == r) {
		st1[id] = v;
		return;
	}
	ll mid = (l + r) / 2;
	upd1(id * 2, l, mid, i, v);
	upd1(id * 2 + 1, mid + 1, r, i, v);
	st1[id] = max(st1[id * 2], st1[id * 2 + 1]);
}

void upd2(ll id, ll l, ll r, ll i, pii v) {
	if (i > r || i < l) return;
	if (l == r) {
		st2[id] = v;
		return;
	}
	ll mid = (l + r) / 2;
	upd2(id * 2, l, mid, i, v);
	upd2(id * 2 + 1, mid + 1, r, i, v);
	st2[id] = min(st2[id * 2], st2[id * 2 + 1]);
}

pii get1(ll id, ll l, ll r, ll L, ll R) {
	if (l > R || r < L) {
		return {0, 0};
	}
	if (L <= l && r <= R) {
		return st1[id];
	}
	ll mid = (l + r) / 2;
	return max(get1(id * 2, l, mid, L, R), get1(id * 2 + 1, mid + 1, r, L, R));
}

pii get2(ll id, ll l, ll r, ll L, ll R) {
	if (l > R || r < L) {
		return {inf, 0};
	}
	if (L <= l && r <= R) {
		return st2[id];
	}
	ll mid = (l + r) / 2;
	return min(get2(id * 2, l, mid, L, R), get2(id * 2 + 1, mid + 1, r, L, R));
}

bool vst[N];
ll num[N];

vector<ll> vt[2];

void dfs(ll u) {
	//cout << "choi " << u << " " << num[u] << endl;
	vst[u] = 1;
	vt[num[u]].push_back(u);
	upd1(1, 1, 2 * n, a[u], {0, 0});
	upd2(1, 1, 2 * n, b[u], {inf, 0});
	while (true) {
		pii x1 = get1(1, 1, 2 * n, a[u] + 1, b[u] - 1);
		if (x1.fi > b[u]) {
			ll v = x1.se;
			num[v] = 1 - num[u];
			dfs(v);
		}
		else {
			pii x2 = get2(1, 1, 2 * n, a[u] + 1, b[u] - 1);
			if (x2.fi < a[u]) {
				ll v = x2.se;
				num[v] = 1 - num[u];
				dfs(v);
			}
			else {
				break;
			}
		}
	}
}

bool cmp(ll u, ll v) {
	if (a[u] == a[v]) {
		return b[u] < b[v];
	}
	return a[u] < a[v];
}

bool klinh;

signed main(void) {
    faster;
    
   	cin >> n;
   	for (int i = 0; i < 4 * N; i ++) {
   		st2[i] = {inf, 0};
   	}
   	for (int i = 1; i <= n; i ++) {
   		cin >> a[i] >> b[i];
   		upd1(1, 1, 2 * n, a[i], {b[i], i});
   		upd2(1, 1, 2 * n, b[i], {a[i], i});
   	}
   	
   	ll ans = 1;
   	for (int i = 1; i <= n; i ++) {
   		if (vst[i] == 1) continue;
   		vt[0].clear();
   		vt[1].clear();
   		dfs(i);
   		//continue;
   		for (int j = 0; j < 2; j ++) {
   			sort(vt[j].begin(), vt[j].end(), cmp);
   			stack<ll> st;
   			for (auto k : vt[j]) {
   				//cout << k << " ";
   				//continue;
   				while (st.size() && b[st.top()] < a[k]) {
   					st.pop();
   				}
   				//continue;
   				if (st.size() && b[st.top()] < b[k]) {
   					cout << 0;
   					exit(0);
   				}
   				//continue;
   				st.push(k);
   			}
   			//cout << endl;
   			//continue;
   		}
   		ans = ans + ans;
   		if (ans >= mod) {
   			ans -= mod;
   		}
   	}
    
    cout << ans;
   	
    cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
    return 0;
}

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