제출 #87489

#제출 시각아이디문제언어결과실행 시간메모리
87489tieunhiPort Facility (JOI17_port_facility)C++14
78 / 100
255 ms61040 KiB
#include <bits/stdc++.h> #define pii pair<int, int> #define mp make_pair #define F first #define S second #define PB push_back #define FOR(i, u, v) for (int i = u; i <= v; i++) #define FORD(i, v, u) for (int i = v; i >= u; i--) #define ll long long #define mid (r + l)/2 #define N 200005 #define LN 19 #define maxc 1000000007 using namespace std; int n, pos[N], a[N], dd[N]; pii seg[N]; struct IntervalTree { int tmin[N << 2], tmax[N << 2]; void calc(int id) { tmin[id] = min(tmin[id*2], tmin[id*2+1]); tmax[id] = max(tmax[id*2], tmax[id*2+1]); } void build(int l, int r, int id) { if (l == r) { tmin[id] = tmax[id] = a[l]; return; } build(l, mid, id*2); build(mid+1, r, id*2+1); calc(id); } void disable(int l, int r, int id, int x) { if (l == r) { tmin[id] = maxc; tmax[id] = 0; return; } if (x <= mid) disable(l, mid, id*2, x); else disable(mid+1, r, id*2+1, x); calc(id); } int getMin(int l, int r, int id, int x, int y) { if (l > y || r < x) return maxc; if (l >= x && r <= y) return tmin[id]; return min(getMin(l, mid, id*2, x, y), getMin(mid+1, r, id*2+1, x, y)); } int getMax(int l, int r, int id, int x, int y) { if (l > y || r < x) return 0; if (l >= x && r <= y) return tmax[id]; return max(getMax(l, mid, id*2, x, y), getMax(mid+1, r, id*2+1, x, y)); } }t; void stop() {cout <<0; exit(0);} void DFS(int u, int col) { dd[u] = col; t.disable(1, 2*n, 1, seg[u].F); t.disable(1, 2*n, 1, seg[u].S); while (1) { int l = t.getMin(1, 2*n, 1, seg[u].F, seg[u].S); if (l >= seg[u].F) break; int v = pos[l]; if (dd[v] != -1) if (dd[v] != (col^1)) stop(); DFS(v, col^1); } while (1) { int r = t.getMax(1, 2*n, 1, seg[u].F, seg[u].S); if (r <= seg[u].S) break; int v = pos[r]; if (dd[v] != -1) if (dd[v] != (col^1)) stop(); DFS(v, col^1); } } bool check() { stack<int> v[2]; FOR(i, 1, 2*n) { int u = pos[i]; int type = dd[u]; if (i == seg[u].F) v[type].push(u); else { if (v[type].top() != u) return 0; v[type].pop(); } } return 1; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("INP.TXT", "r", stdin); cin >> n; FOR(i, 1, n) { int u, v; cin >> u >> v; seg[i] = mp(u, v); } sort(seg+1, seg+n+1); FOR(i, 1, n) { int u = seg[i].F, v = seg[i].S; a[u] = v; a[v] = u; pos[u] = pos[v] = i; } t.build(1, 2*n, 1); memset(dd, -1, sizeof dd); int res = 1; FOR(i, 1, n) { if (dd[i] != -1) continue; DFS(i, 0); res = (res*2) % maxc; } if (check()) cout <<res; else stop(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...