Submission #1044701

#TimeUsernameProblemLanguageResultExecution timeMemory
1044701SharkyPort Facility (JOI17_port_facility)C++17
100 / 100
2163 ms382024 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const ll mod = 1e9 + 7; const int N = (1 << 21) + 10; int p[2 * N], sz[2 * N], pt[2 * N], a[N], b[N], cc = 0; set<int> disc; vector<int> seg[2 * N]; ll ans = 1; int n; int find(int u) { return p[u] == u ? u : p[u] = find(p[u]); } void merge(int u, int v) { u = find(u), v = find(v); if (u == v) return; if (sz[u] < sz[v]) swap(u, v); p[v] = u; sz[u] += sz[v]; } void update(int pos, int val, int l = 1, int r = 2 * n, int id = 1) { seg[id].push_back(val); if (l == r) return; int mid = (l + r) / 2; if (pos <= mid) update(pos, val, l, mid, id * 2); else update(pos, val, mid + 1, r, id * 2 + 1); } void query(int ql, int qr, int val, int l = 1, int r = 2 * n, int id = 1) { if (ql > qr || qr < l || r < ql || seg[id].empty()) return; if (ql <= l && r <= qr) { merge(val, seg[id][0] + n); merge(val + n, seg[id][0]); for (int i = pt[id] + 1; i < seg[id].size(); i++) { merge(seg[id][i-1], seg[id][i]); merge(seg[id][i-1] + n, seg[id][i] + n); pt[id]++; } return; } int mid = (l + r) / 2; query(ql, qr, val, l, mid, id * 2); query(ql, qr, val, mid + 1, r, id * 2 + 1); } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; vector<int> idx; for (int i = 1; i <= n; i++) { cin >> a[i] >> b[i]; idx.push_back(i); } iota(p, p + 2 * N, 0); fill(sz, sz + 2 * N, 1); sort(idx.begin(), idx.end(), [&] (auto x, auto y) { return a[x] < a[y]; }); for (int i : idx) { query(a[i], b[i], i); update(b[i], i); } for (int i = 1; i <= n; i++) { if (find(i) == find(i + n)) { cout << "0\n"; return 0; } } for (int i = 1; i <= 2 * n; i++) { int x = find(i); if (x > n) x -= n; disc.insert(x); } int sz = (int) disc.size(); while (sz--) (ans *= 2LL) %= mod; cout << ans << '\n'; }

Compilation message (stderr)

port_facility.cpp: In function 'void query(int, int, int, int, int, int)':
port_facility.cpp:40:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for (int i = pt[id] + 1; i < seg[id].size(); i++) {
      |                                  ~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...