이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n) { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }
#define BitCount(x) __builtin_popcount(x)
using namespace std;
typedef pair <int, int> II;
typedef long long LL;
const int N = 2 * (1e6 + 10);
const int LG = 25;
const int INF = 0x3f3f3f3f;
const int BASE = 1e9 + 7;
int n;
int a[N], L[N], R[N], pos[N], p[N];
bool fre[N];
vector <int> adj[N];
struct Segment {
int l, r;
Segment () {}
Segment (int l, int r) : l(l), r(r) {}
bool operator < (const Segment &that) const {
return l < that.l;
}
} seg[N];
struct DSU {
int p[N];
void Init() {
memset(p, -1, sizeof p);
}
int Root(int u) {
return p[u] < 0 ? u : p[u] = Root(p[u]);
}
void Union(int u, int v) {
u = Root(u); v = Root(v);
if (u == v) return;
if (p[u] > p[v]) swap(u, v);
p[u] += p[v];
p[v] = u;
}
} DSU;
set <int> S;
int Find(int v) {
set <int> :: iterator it = S.lower_bound(v);
if (it == S.begin()) return -1;
else return *(--it);
}
struct RMQ {
int lg[N];
int spT[2][N][LG];
void Init() {
FOR(i, 1, 2 * n) {
spT[0][i][0] = (a[i] > i ? a[i] : 0);
spT[1][i][0] = ((a[i] != 0 && a[i] < i) ? a[i] : INF);
}
for (int j = 1; 1 << j <= 2 * n; ++j)
for (int i = 1; i + (1 << j) - 1 <= 2 * n; ++i) {
spT[0][i][j] = max(spT[0][i][j - 1], spT[0][i + (1 << (j - 1))][j - 1]);
spT[1][i][j] = min(spT[1][i][j - 1], spT[1][i + (1 << (j - 1))][j - 1]);
}
for (int i = 0; 1 << i <= 2 * n; ++i) lg[1 << i] = i;
FOR(i, 1, 2 * n) if (!lg[i]) lg[i] = lg[i - 1];
}
int Query(int t, int l, int r) {
int k = lg[r - l + 1];
if (t == 0)return max(spT[t][l][k], spT[t][r - (1 << k) + 1][k]);
else return min(spT[t][l][k], spT[t][r - (1 << k) + 1][k]);
}
} RMQ;
bool Intersect(int x, int y) {
int l1 = L[x], r1 = R[x];
int l2 = L[y], r2 = R[y];
if (l2 > r1 || r2 < l1) return false;
if (l1 < l2 && r2 < r1) return false;
if (l2 < l1 && r1 < r2) return false;
return true;
}
bool CMP(int x, int y) {
if (L[x] != L[y]) return L[x] < L[y];
return R[x] < R[y];
}
bool cycle = false;
void DFS(int u, int par = -1) {
DEBUG(u);
fre[u] = true;
REP(k, 0, adj[u].size()) {
int v = adj[u][k]; if (v == par) continue;
if (fre[v] == false) DFS(v, u);
else {
cout << u << " " << v << endl;
cycle = true;
}
}
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // LOCAL
scanf("%d", &n);
FOR(i, 1, n) {
int l, r; scanf("%d%d", &l, &r);
seg[i] = Segment(l, r);
a[l] = r;
a[r] = l;
pos[l] = i;
pos[r] = i;
}
RMQ.Init();
DSU.Init();
sort(seg + 1, seg + n + 1);
// FOR(i, 1, n) cout << seg[i].l << " " << seg[i].r << endl;
//cout << endl;
FOR(i, 1, n)
FOR(j, i + 1, n) if (seg[j].l < seg[i].r && seg[j].r > seg[i].r) {
// adj[i].push_back(j);
// adj[j].push_back(i);
int r1 = DSU.Root(i), r2 = DSU.Root(j);
// cout << i << " " << j << endl;
if (r1 != r2) DSU.Union(i, j);
else {
puts("0");
return 0;
}
}
DSU.Init();
/* FOR(timer, 1, 2 * n) {
assert(a[timer] != 0);
if (a[timer] > timer) {
int l2 = timer, r2 = a[timer];
int r1 = Find(r2);
if (r1 != -1) {
if (l2 < r1 && RMQ.Query(0, l2, r1) > r2) {
puts("0");
return 0;
}
}
S.insert(a[timer]);
} else {
S.erase(timer);
}
}*/
int fre = 0;
FOR(timer, 1, 2 * n) {
if (a[timer] > timer) {
int l = timer, r = a[timer];
int lMin = RMQ.Query(1, l, r), rMax = RMQ.Query(0, l, r);
if (lMin < l) DSU.Union(pos[timer], pos[lMin]);
if (rMax > r) DSU.Union(pos[timer], pos[rMax]);
}
}
int cmp = 0;
FOR(i, 1, n) if (DSU.p[i] < 0) ++cmp;
int ans = 1;
FOR(i, 1, cmp) ans = (LL)ans * 2 % BASE;
cout << ans;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
port_facility.cpp: In function 'void DFS(int, int)':
port_facility.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define REP(x, a, b) for (int x = a; x < b; ++x)
^
port_facility.cpp:104:5: note: in expansion of macro 'REP'
REP(k, 0, adj[u].size()) {
^
port_facility.cpp: In function 'int main()':
port_facility.cpp:163:9: warning: unused variable 'fre' [-Wunused-variable]
int fre = 0;
^
port_facility.cpp:119:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
port_facility.cpp:121:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int l, r; scanf("%d%d", &l, &r);
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |