제출 #532135

#제출 시각아이디문제언어결과실행 시간메모리
532135K4YANPort Facility (JOI17_port_facility)C++17
100 / 100
5846 ms117172 KiB
//Be Name Khoda #include<bits/stdc++.h> #pragma GCC optmize("Ofast,unroll-loops") #pragma GCC target ("avx2,tune=native") using namespace std; #define ll long long #define ld long double #define all(x) x.begin(), x.end() #define pii pair<int, int> #define pll pair<ll, ll> #define plll pair<pll, ll> const ll mxn = 2e6 + 16, md = 1e9 + 7;//9:55 int n, m, q, w; int clr[mxn]; vector<int> A, B; bitset<mxn> mark; void input() { cin >> n; for(int i = 0; i < n; i++) { cin >> q; q--; A.push_back(q); cin >> q; q--; B.push_back(q); } } struct item { int mn, mx, type; }; struct item2 { int n0, n1; }; struct segtree { int sz = 1; item NE = {mxn, -1, -1}; item2 NE2 = {mxn, mxn}; vector<item> v; vector<item2> osc; void init(int n) { while(sz < n) sz <<= 1; v.assign(2 * sz, NE); osc.assign(2 * sz, NE2); } void update(int x) { v[x].mn = min(v[2 * x + 1].mn, v[2 * x + 2].mn); v[x].mx = max(v[2 * x + 1].mx, v[2 * x + 2].mx); osc[x].n0 = min(osc[2 * x + 1].n0, osc[2 * x + 2].n0); osc[x].n1 = min(osc[2 * x + 1].n1, osc[2 * x + 2].n1); return; } void add(int i, pii p, int x, int lx, int rx) { if(rx - lx == 1) { if(p.second == 0) osc[x].n0 = p.first; else osc[x].n1 = p.first; return; } int m = (lx + rx) >> 1; if(i < m) add(i, p, 2 * x + 1, lx, m); else add(i, p, 2 * x + 2, m, rx); update(x); } void add(int i, pii p) { add(i, p, 0, 0, sz); return; } int SAGZAN(int l, int r, int typ, int x, int lx, int rx) { if(rx <= l || r <= lx) return mxn; if(l <= lx && rx <= r) { if(typ == 0) return osc[x].n0; return osc[x].n1; } int m = (lx + rx) >> 1; int ans = SAGZAN(l, r, typ, 2 * x + 1, lx, m); ans = min(ans, SAGZAN(l, r, typ, 2 * x + 2, m, rx)); return ans; } int SAGZAN(int l, int r, int typ) { return SAGZAN(l, r, typ, 0, 0, sz); } void add_to_mn(int i, pii p, int x, int lx, int rx) { if(rx - lx == 1) { v[x].mn = p.first, v[x].type = p.second; return; } int m = (lx + rx) >> 1; if(i < m) add_to_mn(i, p, 2 * x + 1, lx, m); else add_to_mn(i, p, 2 * x + 2, m, rx); v[x].mn = min(v[2 * x + 1].mn, v[2 * x + 2].mn); return; } void add_to_mn(int i, pii p) { add_to_mn(i, p, 0, 0, sz); return; } void add_to_mx(int i, pii p, int x, int lx, int rx) { if(rx - lx == 1) { v[x].mx = p.first, v[x].type = p.second; return; } int m = (lx + rx) >> 1; if(i < m) add_to_mx(i, p, 2 * x + 1, lx, m); else add_to_mx(i, p, 2 * x + 2, m, rx); v[x].mx = max(v[2 * x + 1].mx, v[2 * x + 2].mx); return; } void add_to_mx(int i, pii p) { add_to_mx(i, p, 0, 0, sz); return; } pii find_mn(int l, int r, int x, int lx, int rx) { if(rx <= l || r <= lx) return {mxn, -1}; if(rx - lx == 1) { if(v[x].mn < l - 1) { return {v[x].mn, v[x].type}; } return {mxn, -1}; } int m = (lx + rx) >> 1; if(l <= lx && rx <= r) { if(v[2 * x + 2].mn < l - 1) { return find_mn(l, r, 2 * x + 2, m, rx); } if(v[2 * x + 1].mn < l - 1) { return find_mn(l, r, 2 * x + 1, lx, m); } return {mxn, -1}; } pii p = find_mn(l, r, 2 * x + 2, m, rx); if(p.first < mxn) return p; p = find_mn(l, r, 2 * x + 1, lx, m); return p; } pii find_mn(int l, int r) { return find_mn(l, r, 0, 0, sz); } pii find_mx(int l, int r, int x, int lx, int rx) { if(rx <= l || r <= lx) return {-1, -1}; if(rx - lx == 1) { if(v[x].mx > r) { return {v[x].mx, v[x].type}; } return {-1, -1}; } int m = (lx + rx) >> 1; if(l <= lx && rx <= r) { if(v[2 * x + 1].mx > r) { return find_mx(l, r, 2 * x + 1, lx, m); } if(v[2 * x + 2].mx > r) { return find_mx(l, r, 2 * x + 2, m, rx); } return {-1, -1}; } pii p = find_mx(l, r, 2 * x + 1, lx, m); if(p.first > -1) return p; p = find_mx(l, r, 2 * x + 2, m, rx); return p; } pii find_mx(int l, int r) { return find_mx(l, r, 0, 0, sz); } void set(int i, int x, int lx, int rx) { if(rx - lx == 1) { v[x] = NE; return; } int m = (lx + rx) >> 1; if(i < m) set(i, 2 * x + 1, lx, m); else set(i, 2 * x + 2, m, rx); update(x); return; } void set(int i) { set(i, 0, 0, sz); return; } }; segtree st; inline void BFS(int i) { vector<int> bfs; bfs.push_back(i); int ptr = 0, x; pll p; st.set(A[i]), st.set(B[i]); while(ptr < int(bfs.size())) { x = bfs[ptr++]; mark.set(x); p = {0, 0}; while(p.second > -1) { p = st.find_mx(A[x] + 1, B[x]); if(p.second == -1 || p.first == -1) break; bfs.push_back(p.second); st.set(A[p.second]), st.set(B[p.second]); } p = {0, 0}; while(p.second > -1) { p = st.find_mn(A[x] + 1, B[x]); if(p.second == -1 || p.first == mxn) break; bfs.push_back(p.second); st.set(A[p.second]), st.set(B[p.second]); } } return; } inline void BFS_0(int i) { vector<int> bfs; bfs.push_back(i); int ptr = 0, x; pll p; st.set(A[i]), st.set(B[i]); while(ptr < int(bfs.size())) { x = bfs[ptr++]; mark.set(x); p = {0, 0}; while(p.second > -1) { p = st.find_mx(A[x] + 1, B[x]); if(p.second == -1 || p.first == -1) break; bfs.push_back(p.second); clr[p.second] = clr[x] ^ 1; st.set(A[p.second]), st.set(B[p.second]); } p = {0, 0}; while(p.second > -1) { p = st.find_mn(A[x] + 1, B[x]); if(p.second == -1 || p.first == mxn) break; bfs.push_back(p.second); clr[p.second] = clr[x] ^ 1; st.set(A[p.second]), st.set(B[p.second]); } } return; } void solve() { st.init(2 * n); for(int i = 0; i < n; i++) { st.add_to_mn(B[i], {A[i], i}); st.add_to_mx(A[i], {B[i], i}); } for(int i = 0; i < n; i++) { if(!mark[i]) { BFS_0(i); } } mark.reset(); for(int i = 0; i < n; i++) { st.add(B[i], {A[i], clr[i]}); } for(int i = 0; i < n; i++) { q = st.SAGZAN(A[i] + 1, B[i], clr[i]); if(q < A[i]) { cout << "0\n"; return; } } for(int i = 0; i < n; i++) { st.add_to_mn(B[i], {A[i], i}); st.add_to_mx(A[i], {B[i], i}); } ll cnt = 0, ans = 1; for(int i = 0; i < n; i++) { if(!mark[i]) { BFS(i); cnt++; } } for(int i = 0; i < cnt; i++) { ans <<= 1; ans %= md; } cout << ans << endl; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); input(), solve(); return 0; }

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

port_facility.cpp:4: warning: ignoring '#pragma GCC optmize' [-Wunknown-pragmas]
    4 | #pragma GCC optmize("Ofast,unroll-loops")
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...