제출 #533842

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
533842		Arnch	Port Facility (JOI17_port_facility)	C++17	0 / 100	0 ms	332 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")

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 << 2];
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;
}

void DFS(int x) {
	mark[x] = 1;
	change(1, 2 * n + 1, a[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);
	}
}

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];
}

ll poww(ll x, int y) {
	ll res = 1;
	for(; y; y /= 2, x = x * x % mod)
		if(y & 1) {
			res = res * x % mod;
		}
	return res;
}

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

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

	sort(All(res), cmp2);
	
	int colorcnt = 0;
	for(auto i : res) {
		if(mark[i]) continue;
		DFS(i);
		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<<poww(2, colorcnt);

    return 0;
}

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