제출 #834000

#제출 시각아이디문제언어결과실행 시간메모리
834000LucaIliePort Facility (JOI17_port_facility)C++17
78 / 100
6030 ms117732 KiB
#include <bits/stdc++.h> using namespace std; const int MAX_N = 1e6; const int INF = 1e9; const int MOD = 1e9 + 7; int n; bool bipartit = true; bool vis[MAX_N], side[MAX_N]; int l[MAX_N], r[MAX_N]; int indexL[2 * MAX_N + 1], indexR[2 * MAX_N + 1]; struct SEG_TREE { int segTree[4 * MAX_N]; void init() { for ( int v = 0; v < 4 * MAX_N; v++ ) segTree[v] = -INF; } void update( int v, int l, int r, int pos, int x ) { if ( l > pos || r < pos ) return; if ( l == r ) { segTree[v] = x; return; } int mid = (l + r) / 2; update( v * 2 + 1, l, mid, pos, x ); update( v * 2 + 2, mid + 1, r, pos, x ); segTree[v] = max( segTree[v * 2 + 1], segTree[v * 2 + 2] ); } int query( int v, int l, int r, int lq, int rq ) { if ( l > rq || r < lq ) return -INF; if ( lq <= l && r <= rq ) return segTree[v]; int mid = (l + r) / 2; return max( query( v * 2 + 1, l, mid, lq, rq ), query( v * 2 + 2, mid + 1, r, lq, rq ) ); } }; SEG_TREE unvisitedByL, unvisitedByR, visitedByL0, visitedByR0, visitedByL1, visitedByR1; void checkBipartit( int u ) { vis[u] = true; unvisitedByL.update( 0, 1, 2 * n, l[u], -INF ); unvisitedByR.update( 0, 1, 2 * n, r[u], -INF ); if ( side[u] == 0 ) { visitedByL0.update( 0, 1, 2 * n, l[u], r[u] ); visitedByR0.update( 0, 1, 2 * n, r[u], -l[u] ); } else { visitedByL1.update( 0, 1, 2 * n, l[u], r[u] ); visitedByR1.update( 0, 1, 2 * n, r[u], -l[u] ); } while ( unvisitedByL.query( 0, 1, 2 * n, l[u], r[u] ) > r[u] ) { int v = indexR[unvisitedByL.query( 0, 1, 2 * n, l[u], r[u] )]; side[v] = side[u] ^ 1; checkBipartit( v ); } while ( -unvisitedByR.query( 0, 1, 2 * n, l[u], r[u] ) < l[u] ) { int v = indexL[-unvisitedByR.query( 0, 1, 2 * n, l[u], r[u] )]; side[v] = side[u] ^ 1; checkBipartit( v ); } bool exista0 = false, exista1 = false; if ( visitedByL0.query( 0, 1, 2 * n, l[u], r[u] ) > r[u] || -visitedByR0.query( 0, 1, 2 * n, l[u], r[u] ) < l[u] ) exista0 = true; if ( visitedByL1.query( 0, 1, 2 * n, l[u], r[u] ) > r[u] || -visitedByR1.query( 0, 1, 2 * n, l[u], r[u] ) < l[u] ) exista1 = true; if ( exista0 && exista1 ) bipartit = false; } int main() { cin.tie( NULL ); cout.tie( NULL ); ios_base::sync_with_stdio( false ); cin >> n; for ( int i = 0; i < n; i++ ) cin >> l[i] >> r[i]; unvisitedByL.init(); unvisitedByR.init(); visitedByL0.init(); visitedByR0.init(); visitedByL1.init(); visitedByR1.init(); for ( int i = 0; i < n; i++ ) { unvisitedByL.update( 0, 1, 2 * n, l[i], r[i] ); unvisitedByR.update( 0, 1, 2 * n, r[i], -l[i] ); indexL[l[i]] = i; indexR[r[i]] = i; } int comp = 0; for ( int u = 0; u < n; u++ ) { if ( !vis[u] ) { side[u] = 0; checkBipartit( u ); comp++; } } if ( bipartit ) { int ans = 1; for ( int i = 0; i < comp; i++ ) ans = ans * 2 % MOD; cout << ans; } else cout << 0; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...