제출 #24293

#제출 시각아이디문제언어결과실행 시간메모리
24293jiaqiyangPort Facility (JOI17_port_facility)C++14
0 / 100
29 ms141800 KiB
#include <cctype> #include <cstdio> #include <cstdlib> #include <cstring> #include <vector> int nextInt() { char ch; while (!isdigit(ch = getchar())) {} int res = ch - '0'; while (isdigit(ch = getchar())) res = 10 * res + ch - '0'; return res; } const int N = 2000000 + 10, MOD = 1000000007; int n, a[N], b[N], c[N], id[N]; std::vector<int> adj[N]; void link(int a, int b) { adj[a].push_back(b); adj[b].push_back(a); } std::vector<int> pool[N]; void update(int p, int v) { for (; p <= 2 * n; p += p & -p) pool[p].push_back(v); } void query(int p, int v) { for (; p; p ^= p & -p) { if (pool[p].empty()) continue; int x = pool[p].back(); if (b[x] < a[v]) continue; for (; !pool[p].empty(); pool[p].pop_back()) { int u = pool[p].back(); if (b[u] >= a[v]) link(u, v); } pool[p].push_back(x); } } int tag[N]; void fail() { puts("0"); exit(0); } void dfs(int a) { int c = 3 - tag[a]; for (auto b : adj[a]) { if (!tag[b]) { tag[b] = c; dfs(b); } else if (tag[b] != c) { fail(); } } } class { int data[N]; void add(int p, int v) { for (; p <= 2 * n; p += p & -p) data[p] += v; } public: void clear() { memset(data, 0, sizeof data); } void add(int l, int r, int v) { add(l, v); add(r + 1, -v); } int query(int p) { int res = 0; for (; p; p ^= p & -p) res += data[p]; return res; } } bit; void check(int y) { bit.clear(); for (int i = 1; i <= 2 * n; ++i) { int x = id[i]; if (tag[x] != y) continue; if (c[i] > i) { bit.add(1, i, 1); } else { bit.add(1, c[i], -1); if (bit.query(c[i])) fail(); bit.add(c[i], i, 1); } } } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) a[i] = nextInt(), b[i] = nextInt(); for (int i = 1; i <= n; ++i) c[a[i]] = b[i], c[b[i]] = a[i], id[a[i]] = id[b[i]] = i; for (int i = 1; i <= 2 * n; ++i) { if (c[i] > i) continue; query(c[i], id[i]); update(c[i], id[i]); } int cnt = 0; for (int i = 1; i <= n; ++i) if (!tag[i]) ++cnt, tag[i] = 1, dfs(i); check(1); check(2); int ans = 1; while (cnt--) ans = 2 * ans % MOD; printf("%d\n", ans); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

port_facility.cpp: In function 'int main()':
port_facility.cpp:100:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
                  ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...