Submission #533854

#	Time	Username	Problem	Language	Result	Execution time	Memory
533854		Arnch	Port Facility (JOI17_port_facility)	C++17	100 / 100	3829 ms	167984 KiB

port_facility

// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")
#pragma GCC optimze("Ofast")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()

constexpr ll inf = 1e18, N = 1e6 + 10, mod = 1e9 + 7, pr = 1000696969;

int n, a[N], b[N];
bool mark[N], color[N];

struct node {
	int pos;
} x[N << 4];
void change(int l, int r, int ind, int pos, int v) {
	if(r - l < 2) {
		x[v].pos = pos;
		return;
	}
	int mid = (l + r) / 2;
	if(ind < mid) change(l, mid, ind, pos, 2 * v);
	else change(mid, r, ind, pos, 2 * v + 1);
	if(b[x[2 * v].pos] > b[x[2 * v + 1].pos]) x[v].pos = x[2 * v].pos;
	else x[v].pos = x[2 * v + 1].pos;
}
int get(int l, int r, int s, int e, int v) {
	if(r <= s || l >= e) return 0;
	if(l >= s && r <= e) {
		return x[v].pos;
	}
	int mid = (l + r) >> 1;
	int pl = get(l, mid, s, e, 2 * v), pr = get(mid, r, s, e, 2 * v + 1);
	if(b[pl] >= b[pr]) return pl;
	else return pr;
}

struct node2 {
	int pos;
} x2[N << 4];
void change2(int l, int r, int ind, int pos, int v) {
	if(r - l < 2) {
		x2[v].pos = pos;
		return;
	}
	int mid = (l + r) / 2;
	if(ind < mid) change2(l, mid, ind, pos, 2 * v);
	else change2(mid, r, ind, pos, 2 * v + 1);
	if(a[x2[2 * v].pos] < a[x2[2 * v + 1].pos]) x2[v].pos = x2[2 * v].pos;
	else x2[v].pos = x2[2 * v + 1].pos;
}
int get2(int l, int r, int s, int e, int v) {
	if(r <= s || l >= e) return 0;
	if(l >= s && r <= e) {
		return x2[v].pos;
	}
	int mid = (l + r) >> 1;
	int pl = get2(l, mid, s, e, 2 * v), pr = get2(mid, r, s, e, 2 * v + 1);
	if(a[pl] <= a[pr]) return pl;
	else return pr;
}

void DFS(int x) {
	mark[x] = 1;
	change(1, 2 * n + 1, a[x], 0, 1);
	change2(1, 2 * n + 1, b[x], 0, 1);
	while(true) {
		int ans = get(1, 2 * n + 1, a[x] + 1, b[x], 1);
		if(b[ans] <= b[x]) {
			break;
		}
		color[ans] = 1 - color[x];
		DFS(ans);
	}
	while(true) {
		int ans = get2(1, 2 * n + 1, a[x] + 1, b[x], 1);
		if(a[ans] >= a[x]) break;
		color[ans] = 1 - color[x];
		DFS(ans);
	}
}

bool cmp(pair<int, int> p1, pair<int, int> p2) {
	int cnt1 = 0, cnt2 = 0;
	if(p1.second == 0) cnt1 = a[p1.first];
	else cnt1 = b[p1.first];
	if(p2.second == 0) cnt2 = a[p2.first];
	else cnt2 = b[p2.first];
	return cnt1 < cnt2;
}

bool cmp2(int i, int j) {
	return a[i] < a[j];
}

void mkay(ll &a) {
	while(a > mod) a -= mod;
}

int main() {
    ios :: sync_with_stdio(0), cin.tie(0);

	vector<int> res;
	cin >>n;
	a[0] = 1e9;
	for(int i = 1; i <= n; i++) {
		cin >>a[i] >>b[i];
		change(1, 2 * n + 1, a[i], i, 1);
		change2(1, 2 * n + 1, b[i], i, 1);
	}

	ll ans = 1;
	int colorcnt = 0;
	for(int i = 1; i <= n; i++) {
		if(mark[i]) continue;
		DFS(i);
		mkay(ans *= 2);
		colorcnt++;
	}

	vector<int> c[2]; vector<pair<int, int> > vc;
	for(int i = 1; i <= n; i++) {
		vc.push_back({i, 0});
		vc.push_back({i, 1});
	}
	sort(All(vc), cmp);
	for(auto i : vc) {
		if(i.second == 0) c[color[i.first]].push_back(i.first);
		else {
			if(c[color[i.first]].empty() || c[color[i.first]].back() != i.first) {
				return cout<<0, 0;
			}
			c[color[i.first]].pop_back();
		}
	}

	cout<<ans;
	

    return 0;
}

Compilation message (stderr)

port_facility.cpp:11: warning: ignoring '#pragma GCC optimze' [-Wunknown-pragmas]
   11 | #pragma GCC optimze("Ofast")
      |

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