제출 #850132

#제출 시각아이디문제언어결과실행 시간메모리
850132mickey080929Port Facility (JOI17_port_facility)C++17
10 / 100
6 ms604 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> pii; const int mod = 998'244'353; struct DisjointSet{ public: int n; vector<int> par; void Init(int _n) { n = _n; par.resize(n); iota(par.begin(), par.end(), 0); } int Find(int x) { if (par[x] == x) return x; return par[x] = Find(par[x]); } void Union(int x, int y) { x = Find(x); y = Find(y); if (x == y) return; par[y] = x; } } dsu; struct SegmentTree{ public: int n; vector<int> tree; void Init(int _n) { n = _n; int sz = 1<<(Log2(n)+1); tree.resize(sz); fill(tree.begin(), tree.end(), -1); } void Update(int tar, int val) { Update(1, 1, n, tar, val); } int Query(int l, int r) { return Query(1, 1, n, l, r); } private: static int Log2(int n) { int ret = 0; while (n > 1 << ret) ret ++; return ret; } void Update(int node, int s, int e, int tar, int val) { if (s > tar || tar > e) return; if (s == e) { tree[node] = val; return; } int mid = s + e >> 1; Update(node<<1, s, mid, tar, val); Update(node<<1|1, mid+1, e, tar, val); tree[node] = max(tree[node<<1], tree[node<<1|1]); } int Query(int node, int s, int e, int l, int r) { if (l > e || s > r) return -1; if (l <= s && e <= r) return tree[node]; int mid = s + e >> 1; return max(Query(node<<1, s, mid, l, r), Query(node<<1|1, mid+1, e, l, r)); } } seg; int main() { //ios_base :: sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; vector<pii> a(n); vector<int> chk(2*n, 0); for (int i=0; i<n; i++) { cin >> a[i].first >> a[i].second; } sort(a.begin(), a.end()); seg.Init(2*n); dsu.Init(2*n); for (int i=0; i<n; i++) { vector<int> v; while (true) { int ret = seg.Query(a[i].first, a[i].second); if (ret == -1) break; v.push_back(ret); seg.Update(a[ret].second, -1); } if (!v.empty()) { sort(v.begin(), v.end(), [&] (int &u, int &v) { return a[u].first < a[v].first; }); for (int j=0; j<(int)v.size()-1; j++) { if (a[v[j]].second < a[v[j+1]].second) { cout << "0\n"; return 0; } } for (auto &x : v) { chk[dsu.Find(x<<1)] = 1; if (chk[dsu.Find(x<<1)^1]) { cout << "0\n"; return 0; } } for (auto &x : v) chk[dsu.Find(x<<1)] = 0; int g = dsu.Find(v[0]<<1); for (auto &x : v) { dsu.Union(g, x<<1); dsu.Union(g^1, x<<1^1); } dsu.Union(g^1, i<<1); dsu.Union(g, i<<1^1); for (auto &x : v) seg.Update(a[x].second, x); } seg.Update(a[i].second, i); } int ans = 1; for (int i=0; i<n; i++) { if (dsu.Find(i<<1) == (i<<1)) { ans = ans * 2 % mod; } } cout << ans << '\n'; }

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

port_facility.cpp: In member function 'void SegmentTree::Update(int, int, int, int, int)':
port_facility.cpp:53:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |   int mid = s + e >> 1;
      |             ~~^~~
port_facility.cpp: In member function 'int SegmentTree::Query(int, int, int, int, int)':
port_facility.cpp:61:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |   int mid = s + e >> 1;
      |             ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...