제출 #131744

#제출 시각아이디문제언어결과실행 시간메모리
131744imyujinPort Facility (JOI17_port_facility)C++14
78 / 100
6058 ms127660 KiB
#include <bits/stdc++.h> using namespace std; #define MAXN 1000005 #define fi first #define se second typedef int (*Comp)(int, int); typedef long long lint; typedef pair<int, int> pii; const lint MOD = 1e9 + 7; int N; int A[MAXN], B[MAXN]; int mnseg[8 * MAXN], mxseg[8 * MAXN]; int chk[2 * MAXN]; int mn(int a, int b) { return (b == -1 || (a != -1 && A[a] < A[b])) ? a : b; } int mx(int a, int b) { return (b == -1 || (a != -1 && B[a] > B[b])) ? a : b; } void updseg(int seg[], int idx, int l, int r, int x, int y, Comp cmp) { if(l == r) seg[idx] = y; else { int m = (l + r) / 2; if(x <= m) updseg(seg, idx * 2, l, m, x, y, cmp); else updseg(seg, idx * 2 + 1, m + 1, r, x, y, cmp); seg[idx] = cmp(seg[idx * 2], seg[idx * 2 + 1]); } } int gseg(int seg[], int idx, int l, int r, int x, int y, Comp cmp) { if(x <= l && r <= y) return seg[idx]; if(r < x || y < l) return -1; int m = (l + r) / 2; return cmp(gseg(seg, idx * 2, l, m, x, y, cmp), gseg(seg, idx * 2 + 1, m + 1, r, x, y, cmp)); } int findnode(int x) { int t = gseg(mnseg, 1, 1, 2 * N, A[x] + 1, B[x] - 1, mn); if(t != -1 && A[t] < A[x]) return t; t = gseg(mxseg, 1, 1, 2 * N, A[x] + 1, B[x] - 1, mx); return (t == -1 || B[t] < B[x]) ? -1 : t; } void dfs(int x) { updseg(mnseg, 1, 1, 2 * N, B[x], -1, mn); updseg(mxseg, 1, 1, 2 * N, A[x], -1, mx); for(int t = findnode(x); t != -1; t = findnode(x)) { chk[t] = 3 - chk[x]; dfs(t); } } int main() { lint ans = 1ll; scanf("%d", &N); for(int i = 0; i < N; i++) scanf("%d%d", A + i, B + i); for(int i = 1; i < 8 * N; i++) mnseg[i] = mxseg[i] = -1; for(int i = 0; i < N; i++) { updseg(mnseg, 1, 1, 2 * N, B[i], i, mn); updseg(mxseg, 1, 1, 2 * N, A[i], i, mx); } for(int i = 0; i < N; i++) if(!chk[i]) { chk[i] = 1; dfs(i); ans = ans * 2 % MOD; } vector<pii> s; for(int i = 0; i < N; i++) { s.push_back(make_pair(A[i], i)); s.push_back(make_pair(B[i], i)); } sort(s.begin(), s.end()); vector<int> st[2]; for(auto a : s) { if(A[a.se] == a.fi) st[chk[a.se] - 1].push_back(a.se); else { if(st[chk[a.se] - 1].back() != a.se) { printf("0"); return 0; } st[chk[a.se] - 1].pop_back(); } } printf("%lld", ans); return 0; }

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

port_facility.cpp: In function 'int main()':
port_facility.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",  &N);
  ~~~~~^~~~~~~~~~~
port_facility.cpp:59:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < N; i++) 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...