Submission #161202

#	Time	Username	Problem	Language	Result	Execution time	Memory
161202		amoo_safar	Port Facility (JOI17_port_facility)	C++14	100 / 100	4637 ms	136952 KiB

port_facility

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const ll Mod = 1000000007LL;
const int Maxn = 2e6 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

int T[Maxn], st[Maxn], fn[Maxn];

int seg[4 * Maxn];
void add(int id, int ind, int x, int L, int R){
	if((ind < L) || (R <= ind)) return ;
	if((ind == L) && (R == ind + 1)){
		seg[id] = x;
		return ;
	}
	int mid = (L + R) >> 1;
	add(id << 1, ind, x, L, mid);
	add(id << 1 | 1, ind, x, mid, R);
	seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
}
int get(int id, int l, int r, int L, int R){
	if((r <= L) || (R <= l)) return -1;
	if((l <= L) && (R <= r)) return seg[id];
	int mid = (L + R) >> 1;
	return max(get(id << 1, l, r, L, mid), get(id << 1 | 1, l, r, mid, R));
}

int seg2[4 * Maxn];
void add2(int id, int ind, int x, int L, int R){
	if((ind < L) || (R <= ind)) return ;
	if((ind == L) && (R == ind + 1)){
		seg2[id] = x;
		return ;
	}
	int mid = (L + R) >> 1;
	add2(id << 1, ind, x, L, mid);
	add2(id << 1 | 1, ind, x, mid, R);
	seg2[id] = min(seg2[id << 1], seg2[id << 1 | 1]);
}
int get2(int id, int l, int r, int L, int R){
	if((r <= L) || (R <= l)) return Maxn;
	if((l <= L) && (R <= r)) return seg2[id];
	int mid = (L + R) >> 1;
	return min(get2(id << 1, l, r, L, mid), get2(id << 1 | 1, l, r, mid, R));
}



int mk[Maxn];
void DFS(int u, int c){
	mk[u] = c;
	add(1, st[u], -1, 0, Maxn);
	add2(1, fn[u], Maxn, 0, Maxn);
	int adj;
	while( fn[u] < (adj = get(1, st[u], fn[u], 0, Maxn)) ) DFS(-T[adj], 3 - c);
	while( st[u] > (adj = get2(1, st[u], fn[u], 0, Maxn)) ) DFS(T[adj], 3 - c);
}


stack<ll> A, B;

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	memset(seg, -1, sizeof seg);
	memset(seg2, 31, sizeof seg2);
	
	ll n;
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> st[i] >> fn[i];
		T[st[i]] = i;
		T[fn[i]] = -i;
		add(1, st[i], fn[i], 0, Maxn);
		add2(1, fn[i], st[i], 0, Maxn);
	}
	ll ans = 1;
	for(int i = 1; i <= n; i++)
		if(!mk[i]){
			DFS(i, 1);
			ans = (ans + ans) % Mod;
		}
	
	for(int i = 1; i <= n + n; i++){
		//cerr << T[i] << ' ' << mk[abs(T[i])] << '\n';
		if(T[i] > 0){
			if(mk[T[i]] == 1) A.push(T[i]);
			else B.push(T[i]);
		} else {
			if(mk[-T[i]] == 1){
				if(A.empty() || A.top() != -T[i]) return cout << 0, 0;
				else A.pop();
			} else {
				if(B.empty() || B.top() != -T[i]) return cout << 0, 0;
				else B.pop();
			}
		}
	}
	cout << ans << '\n';	
	
	return 0;
}

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