제출 #533822

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
533822		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, l[N], r[N];
bool mark[N], color[N];

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

void DFS(int x) {
	mark[x] = 1;
	change(1, 2 * n + 1, l[x], 0, 0, 1);
	while(true) {
		pair<int, int> ans = get(1, 2 * n + 1, l[x] + 1, r[x], 1);
		if(ans.first <= r[x]) {
			break;
		}
		color[ans.second] = 1 - color[x];
		DFS(ans.second);
	}
}

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

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);

	cin >>n;
	for(int i = 1; i <= n; i++) {
		cin >>l[i] >>r[i];
		change(1, 2 * n + 1, l[i], r[i], i, 1);
	}
	
	int colorcnt = 0;
	for(int i = 1; i <= n; i++) {
		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