제출 #866746

#제출 시각아이디문제언어결과실행 시간메모리
866746mgl_diamondPort Facility (JOI17_port_facility)C++17
100 / 100
918 ms77924 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ii = pair<int, int>; #define foru(i, l, r) for(int i=(l); i<=(r); ++i) #define ford(i, l, r) for(int i=(l); i>=(r); --i) #define fore(x, v) for(auto &x : v) #define all(x) (x).begin(), (x).end() #define sz(x) (int)(x).size() #define fi first #define se second #define file "input" void setIO() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(file".inp", "r")) { freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout); } } const int MOD = 1e9+7; const int N = 1e6+5; int n, anc[2*N]; ii cont[N]; set<ii> hold; int root(int u) { return anc[u] < 0 ? u : anc[u] = root(anc[u]); } void join(int u, int v) { if ((u = root(u)) == (v = root(v))) return; if (anc[u] > anc[v]) swap(u, v); anc[u] += anc[v]; anc[v] = u; } int main() { setIO(); cin >> n; foru(i, 1, n) { int l, r; cin >> l >> r; cont[i] = {l, r}; } foru(i, 1, 2*n) { anc[i] = -1; } sort(cont+1, cont+n+1); foru(i, 1, n) { int l = cont[i].fi, r = cont[i].se; auto lb = hold.lower_bound({l, 0}); auto rb = hold.lower_bound({r, 0}); if (lb == hold.end() || lb -> first >= r) { hold.insert({r, i}); continue; } while (lb != rb) { // cout << lb -> second << " " << i << "\n"; join(lb -> second, i + n); join(lb -> second + n, i); if (root(lb -> second) == root(prev(rb)->second)) break; ++lb; } hold.insert({r, i}); } foru(i, 1, n) if (root(i) == root(i+n)) { cout << 0; return 0; } int ans = 1; foru(i, 1, n) if (root(i) == i) ans = ans * 2 % MOD; cout << ans; }

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

port_facility.cpp: In function 'void setIO()':
port_facility.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen(file".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
port_facility.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...