제출 #81972

#제출 시각아이디문제언어결과실행 시간메모리
81972aquablitz11Port Facility (JOI17_port_facility)C++14
78 / 100
6066 ms839808 KiB
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; #define x first #define y second #define all(x) x.begin(), x.end() const int N = 1<<20; const int MOD = 1e9+7; int n; pii A[N]; pii ev[N<<1], ev2[N<<1]; int col[N]; vector<pii> seg[N<<2], seg2[N<<2]; int ptr[N<<2], ptr2[N<<2]; void build(vector<pii> seg[], int ptr[], pii ev[], int p=1, int b=0, int e=2*n-1) { if (b == e) { if (ev[b].y == 1) { //printf("pushed (%d) %d %d\n", b, A[ev[b].x].x, A[ev[b].x].y); seg[p].push_back(pii(A[ev[b].x].y, ev[b].x)); } else if (ev[b].y == -1) { //printf("revpushed (%d) %d %d\n", b, 2*n-A[ev[b].x].y-1, 2*n-A[ev[b].x].x-1); seg[p].push_back(pii(2*n-A[ev[b].x].x-1, ev[b].x)); } } else { int m = (b+e)/2; build(seg, ptr, ev, p<<1, b, m); build(seg, ptr, ev, p<<1|1, m+1, e); merge(all(seg[p<<1]), all(seg[p<<1|1]), back_inserter(seg[p])); } ptr[p] = seg[p].size()-1; //printf("node %d [%d,%d]:", p, b, e); //for (auto x : seg[p]) printf(" %d", x); //printf("\n"); } pii amort(vector<pii> seg[], int ptr[], int p, int b, int e) { //printf("amortizing %d %d %d\n", p, b, e); while (ptr[p] >= 0 && col[seg[p][ptr[p]].y]) --ptr[p]; return ptr[p] == -1 ? pii(-1, -1) : seg[p][ptr[p]]; } pii get(vector<pii> seg[], int ptr[], int l, int r, int p=1, int b=0, int e=2*n-1) { if (b > r || e < l) return pii(-1, -1); if (b >= l && e <= r) return amort(seg, ptr, p, b, e); int m = (b+e)/2; return max(get(seg, ptr, l, r, p<<1, b, m), get(seg, ptr, l, r, p<<1|1, m+1, e)); } inline bool intersect(int al, int ar, int bl, int br) { if (bl > ar || br < al) return false; if (bl >= al && br <= ar) return false; if (al >= bl && ar <= br) return false; return true; } void solve(int i, int lv=0) { //for (int j = 0; j < lv; ++j) //printf("| "); //printf("solve %d, color = %d\n", i, col[i]); bool att = true; while (true) { pii ans(-1, -1); if (att) ans = get(seg, ptr, A[i].x, A[i].y); int j = ans.y; if (ans == pii(-1, -1) || !intersect(A[i].x, A[i].y, A[j].x, A[j].y)) { att = false; ans = get(seg2, ptr2, 2*n-A[i].y-1, 2*n-A[i].x-1); } j = ans.y; //for (int j = 0; j < lv; ++j) //printf("| "); //printf("intersect with %d\n", j); if (ans == pii(-1, -1) || !intersect(A[i].x, A[i].y, A[j].x, A[j].y)) break; col[j] = col[i] == 1 ? 2 : 1; solve(j, lv+1); } } int main() { scanf("%d", &n); for (int i = 0; i < n; ++i) { scanf("%d%d", &A[i].x, &A[i].y); ev[--A[i].x] = pii(i, 1); ev[--A[i].y] = pii(i, 2); //printf("%d: %d %d\n", i, A[i].x, A[i].y); int fx = 2*n-A[i].x-1, fy = 2*n-A[i].y-1; ev2[fy] = pii(i, -1); ev2[fx] = pii(i, -2); //printf("%d': %d %d\n", i, fy, fx); } build(seg, ptr, ev); build(seg2, ptr2, ev2); int ans = 1; for (int i = 0; i < n; ++i) { if (!col[i]) { col[i] = 1; solve(i); ans = (ans*2)%MOD; } } stack<int> S[2]; for (int i = 0; i < 2*n; ++i) { int x = ev[i].x, t = ev[i].y; int c = col[x]-1; if (t == 1) S[c].push(x); else { if (S[c].top() != x) { ans = 0; break; } S[c].pop(); } } printf("%d\n", ans); return 0; }

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

port_facility.cpp: In function 'int main()':
port_facility.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
port_facility.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &A[i].x, &A[i].y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...