Submission #427412

#TimeUsernameProblemLanguageResultExecution timeMemory
427412pavementPort Facility (JOI17_port_facility)C++17
0 / 100
4 ms460 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #ifdef _WIN32 #define getchar_unlocked _getchar_nolock #endif //#define int long long #define mp make_pair #define mt make_tuple #define pb push_back #define ppb pop_back #define eb emplace_back #define g0(a) get<0>(a) #define g1(a) get<1>(a) #define g2(a) get<2>(a) #define g3(a) get<3>(a) mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); typedef double db; typedef long long ll; typedef long double ld; typedef pair<int, int> ii; typedef tuple<int, int, int> iii; typedef tuple<int, int, int, int> iiii; typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; int N, ans, lft[2000005], rig[2000005], L[2000005], R[2000005], link[2000005], sz[2000005], r[2000005]; bool inv, col[2000005], vis[2000005], cl[2000005]; vector<ii> curr; set<int> seg; const int MOD = 1e9 + 7; void read(int &v) { v = 0; char ch = getchar_unlocked(); for (; ch < '0' || ch > '9'; ch = getchar_unlocked()); for (; '0' <= ch && ch <= '9'; ch = getchar_unlocked()) v = (v << 3) + (v << 1) + (ch & 15); } bool is(int a, int b) { if (L[a] > L[b]) return is(b, a); return R[b] > R[a] && R[a] > L[b]; } int find(int x) { if (x == link[x]) return x; return link[x] = find(link[x]); } void unite(int a, int b) { a = find(a); b = find(b); if (a == b) return; if (sz[b] > sz[a]) swap(a, b); sz[a] += sz[b]; link[b] = a; } void go(int n); struct node { node *left, *right; list<int> val; node(int S, int E) { if (S == E) return; int M = (S + E) >> 1; left = new node(S, M); right = new node(M + 1, E); } void upd(int S, int E, int p, int idx) { val.pb(idx); if (S == E) return; int M = (S + E) >> 1; if (p <= M) left->upd(S, M, p, idx); else right->upd(M + 1, E, p, idx); } void getall(int S, int E, int l, int r, int curr) { if (l > E || r < S) return; if (l <= S && E <= r) { while (!val.empty() && R[val.back()] > r) { if (!vis[val.back()]) col[val.back()] = col[curr] ^ 1, go(val.back()); else if (col[val.back()] == col[curr]) inv = 1; val.ppb(); } return; } int M = (S + E) >> 1; left->getall(S, M, l, r, curr); right->getall(M + 1, E, l, r, curr); } } *root; struct node2 { node2 *left, *right; list<int> val; node2(int S, int E) { if (S == E) return; int M = (S + E) >> 1; left = new node2(S, M); right = new node2(M + 1, E); } void upd(int S, int E, int p, int idx) { val.pb(idx); if (S == E) return; int M = (S + E) >> 1; if (p <= M) left->upd(S, M, p, idx); else right->upd(M + 1, E, p, idx); } void getall(int S, int E, int l, int r, int curr) { if (l > E || r < S) return; if (l <= S && E <= r) { while (!val.empty() && L[val.back()] < l) { if (!vis[val.back()]) col[val.back()] = col[curr] ^ 1, go(val.back()); else if (col[val.back()] == col[curr]) inv = 1; val.ppb(); } return; } int M = (S + E) >> 1; left->getall(S, M, l, r, curr); right->getall(M + 1, E, l, r, curr); } } *root2; void go(int n) { vis[n] = 1; root->getall(1, 2 * N, L[n], R[n], n); root2->getall(1, 2 * N, L[n], R[n], n); } main() { read(N); root = new node(1, 2 * N); root2 = new node2(1, 2 * N); for (int i = 1; i <= N; i++) { link[i] = i; sz[i] = 1; read(L[i]); read(R[i]); cl[R[i]] = 1; r[L[i]] = r[R[i]] = i; } for (int i = 1; i <= 2 * N; i++) if (cl[i]) root->upd(1, 2 * N, L[r[i]], r[i]); for (int i = 2 * N; i >= 1; i--) if (!cl[i]) root2->upd(1, 2 * N, R[r[i]], r[i]); ans = 1; for (int i = 1; i <= N; i++) if (!vis[i]) go(i), ans *= 2, ans %= MOD; if (inv) return puts("0"), 0; printf("%d\n", ans); //~ for (int i = 1; i <= 2 * N; i++) { //~ if (cl[i]) { //~ int pos = -1, cnt = 0; //~ for (int j = (int)curr.size() - 1; j >= 0; j--) { //~ if (find(r[i]) == find(curr[j].first)) { //~ pos = j; //~ break; //~ } else unite(r[i], curr[j].first), cnt += curr[j].second; //~ } //~ if (pos == -1) while (1) {} //~ for (int k = 0, run = curr.size() - pos; k < run - 1; k++) curr.ppb(); //~ curr.back().second += cnt - 1; //~ if (curr.back().second == 0) curr.ppb(); //~ } else { //~ curr.eb(r[i], 1); //~ } //~ } //~ ans = 1; //~ for (int i = 1; i <= N; i++) //~ if (i == find(i)) ans *= 2, ans %= MOD; //~ printf("%d\n", ans); }

Compilation message (stderr)

port_facility.cpp:133:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  133 | main() {
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...