| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 134850 | E869120 | Port Facility (JOI17_port_facility) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#pragma warning (disable: 4996)
int N, L[1 << 20], R[1 << 20], f[1 << 21], col[1 << 20];
vector<pair<int, int>> A1, A2;
// --------------------------------------- セグ木 A ---------------------------------------
long long datA[25252525]; int elA[5252525], cntA[5252525];
int AA[5252525];
vector<int> IA;
int size_A = 1;
void initA(int sz) {
while (size_A <= sz) size_A *= 2;
}
void preaddA(int px, int py) {
px += size_A;
while (px >= 1) { elA[px]++; px >>= 1; }
}
void calcA() {
for (int i = 0; i < size_A * 2; i++) cntA[i + 1] = cntA[i] + elA[i];
for (int i = 0; i < size_A * 2; i++) elA[i] = cntA[i];
for (int i = 0; i < size_A * 2; i++) AA[i] = elA[i];
}
void addA(int px, int &py, int &ind) {
px += size_A; long long r = ((1LL * py) << 20) + 1LL * ind;
while (px >= 1) {
datA[cntA[px]] = r; cntA[px]++;
px >>= 1;
}
}
void query_A(int &l, int &r, int &x, int a, int b, int u) {
if (l <= a && b <= r) {
while (AA[u] < elA[u + 1] && (datA[AA[u]] >> 20) < x) {
int id = (datA[AA[u]] & 1048575LL);
if (col[id] == -1) IA.push_back(id);
AA[u]++;
}
return;
}
if (b <= l || r <= a) return;
query_A(l, r, x, a, (a + b) >> 1, u * 2);
query_A(l, r, x, (a + b) >> 1, b, u * 2 + 1);
}
void queryA(int cl, int cr, int x) {
// [cl, cr) で x 未満のものを全て push する
IA.clear();
query_A(cl, cr, x, 0, size_A, 1);
}
// --------------------------------------- セグ木 B ---------------------------------------
long long datB[25252525]; int elB[5252525], cntB[5252525];
int AB[5252525];
vector<int> IB;
int size_B = 1;
void initB(int sz) {
while (size_B <= sz) size_B *= 2;
}
void preaddB(int px, int py) {
px += size_B;
while (px >= 1) { elB[px]++; px >>= 1; }
}
void calcB() {
for (int i = 0; i < size_B * 2; i++) cntB[i + 1] = cntB[i] + elB[i];
for (int i = 0; i < size_B * 2; i++) elB[i] = cntB[i];
for (int i = 0; i < size_B * 2; i++) AB[i] = elB[i];
}
void addB(int px, int &py, int &ind) {
px += size_B; long long r = ((1LL * py) << 20) + 1LL * ind;
while (px >= 1) {
datB[cntB[px]] = r; cntB[px]++;
px >>= 1;
}
}
void query_B(int &l, int &r, int &x, int a, int b, int u) {
if (l <= a && b <= r) {
while (AB[u] < elB[u + 1] && (datB[AB[u]] >> 20) < x) {
int id = (datB[AB[u]] & 1048575LL);
if (col[id] == -1) IB.push_back(id);
AB[u]++;
}
return;
}
if (b <= l || r <= a) return;
query_B(l, r, x, a, (a + b) >> 1, u * 2);
query_B(l, r, x, (a + b) >> 1, b, u * 2 + 1);
}
void queryB(int cl, int cr, int x) {
// [cl, cr) で x 未満のものを全て push する
IB.clear();
query_B(cl, cr, x, 0, size_B, 1);
}
struct FastIO {
static void scan(double &x) {
scanf("%lf", &x);
}
template <class Integral>
static void scan(Integral &x) {
int k, m = 1;
x = 0;
for (;;) {
k = getchar_unlocked();
//if (k == '-') {
// m = -1;
// break;
//}
//else
if ('0' <= k && k <= '9') {
x = k - '0';
break;
}
}
for (;;) {
k = getchar_unlocked();
if (k < '0' || k > '9')
break;
x = x * 10 + k - '0';
}
//x *= m;//mul is faster than branch-misprediction penalty (maybe)
}
template <class Arithmetic, class... Rest>
static void scan(Arithmetic &x, Rest&... y) {
scan(x);
scan(y...);
}
static void print(double x, char c) {
printf("%.12f%c", x, c);
}
static void print(const char *x, char c) {
printf("%s%c", x, c);
}
template <class Integral>
static void print(Integral x, char c) {
int s = 0, m = 0;
char f[20];//Is this faster than "static char" ?
if (x < 0) {
m = 1;
x = -x;
}
while (x) {
f[s++] = x % 10;
x /= 10;
}
if (!s)
f[s++] = 0;
if (m) putchar_unlocked('-');
while (s--)
putchar_unlocked(f[s] + '0');
putchar_unlocked(c);
}
template <class Arithmetic>
static void println(Arithmetic x) {
print(x, '\n');
}
};
int main() {
FastIO::scan(N);
for (int i = 1; i <= N; i++) {
FastIO::scan(L[i]);
FastIO::scan(R[i]);
A1.push_back(make_pair(L[i], i)); f[L[i]] = i;
A2.push_back(make_pair(R[i], i)); f[R[i]] = -i;
}
sort(A1.begin(), A1.end());
sort(A2.begin(), A2.end()); reverse(A2.begin(), A2.end());
initA(N * 2 + 1); for (int i = 0; i < A2.size(); i++) { int id = A2[i].second; preaddA(L[id], -R[id]); }
calcA(); for (int i = 0; i < A2.size(); i++) { int id = A2[i].second; addA(L[id], -R[id], id); }
initB(N * 2 + 1); for (int i = 0; i < A1.size(); i++) { int id = A1[i].second; preaddB(R[id], L[id]); }
calcB(); for (int i = 0; i < A1.size(); i++) { int id = A1[i].second; addB(R[id], L[id], id); }
for (int i = 1; i <= N; i++) { col[i] = -1; }
queue<int>Q; int cnts = 0;
for (int t = 1; t <= N; t++) {
if (col[t] != -1) continue;
col[t] = 0; Q.push(t); cnts++;
while (!Q.empty()) {
int pos = Q.front(); Q.pop();
queryA(L[pos], R[pos], -R[pos]);
queryB(L[pos], R[pos], L[pos]);
for (int i : IA) { if (col[i] == -1) { col[i] = (col[pos] ^ 1); Q.push(i); } }
for (int i : IB) { if (col[i] == -1) { col[i] = (col[pos] ^ 1); Q.push(i); } }
}
}
vector<int> S1, S2; bool flag = false;
for (int i = 1; i <= 2 * N; i++) {
int id = abs(f[i]);
if (f[i] > 0) {
if (col[id] == 0) S1.push_back(id);
if (col[id] == 1) S2.push_back(id);
}
if (f[i] < 0) {
if (col[id] == 0) { if (S1.size() == 0 || S1[S1.size() - 1] != id) flag = true; else S1.pop_back(); }
if (col[id] == 1) { if (S2.size() == 0 || S2[S2.size() - 1] != id) flag = true; else S2.pop_back(); }
}
}
int ans = 1; for (int i = 1; i <= cnts; i++) { ans *= 2; ans %= 1000000007; }
if (flag == true) ans = 0;
cout << ans << endl;
return 0;
}