제출 #369773

#제출 시각아이디문제언어결과실행 시간메모리
369773Mamnoon_SiamPort Facility (JOI17_port_facility)C++17
78 / 100
6138 ms695128 KiB
#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx,avx2,fma") #include <bits/stdc++.h> using namespace std; /* sorry, this is the bare minimum :'( */ using ll = long long; using ii = pair<int, int>; using vi = vector<int>; #define all(v) begin(v), end(v) #define sz(v) (int)(v).size() #define fi first #define se second const int N = 1 << 21 | 2; vi ls[N << 1]; int nn = 1, n; int le[N]; vector<ii> g[N]; int ptr[N << 1]; int vis[N], col[N]; int A[N], B[N]; bool bfs(int source) { queue<int> Q; vis[source] = 1; Q.push(source); while(sz(Q)) { int u = Q.front(); Q.pop(); for(ii v : g[u]) { if(vis[v.fi]) { if((col[u] ^ v.se) != col[v.fi]) { return false; } } else { vis[v.fi] = 1; col[v.fi] = col[u] ^ v.se; Q.push(v.fi); } } } return true; } void add_edge(int u, int v, int c) { g[u].emplace_back(v, c); g[v].emplace_back(u, c); } void prefix(int u, int k, int id) { vi& v = ls[u]; int& p = ptr[u]; if(sz(v) and A[v[0]] < k) { add_edge(id, v[0], 1); while(p < sz(v) and A[v[p]] < k) ++p; } } void doshit(int l, int r, int k, int id) { // (l, r), < k for(l += nn, r += nn; l+1 < r; l >>= 1, r >>= 1) { if(~l & 1) prefix(l ^ 1, k, id); if(r & 1) prefix(r ^ 1, k, id); } } int main(int argc, char const *argv[]) { cin.sync_with_stdio(0); cin.tie(0); cin.exceptions(cin.failbit); #ifdef LOCAL freopen("in", "r", stdin); #endif scanf("%d", &n); while(nn < n*2) nn <<= 1; for(int i = 0; i < n; ++i) { scanf("%d %d", &A[i], &B[i]); A[i]--, B[i]--; ls[B[i] + nn].emplace_back(i); } for(int i = nn-1; i >= 1; --i) { merge(all(ls[i<<1]), all(ls[i<<1|1]), back_inserter(ls[i]), [](int x, int y){ return A[x] < A[y]; }); } for(int i = 0; i < n; ++i) { doshit(A[i], B[i], A[i], i); } for(int i = nn-1; i >= 1; --i) { for(int j = 1; j < ptr[i]; ++j) { add_edge(ls[i][j-1], ls[i][j], 0); } } // return 0; const int md = 1e9 + 7; int ans = 1; for(int i = 0; i < n; ++i) { if(!vis[i]) { if(!bfs(i)) { puts("0"); return 0; } else { if((ans <<= 1) >= md) ans -= md; } } } printf("%d\n", ans); return 0; }

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

port_facility.cpp: In function 'int main(int, const char**)':
port_facility.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   77 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
port_facility.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |     scanf("%d %d", &A[i], &B[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...