제출 #234709

#제출 시각아이디문제언어결과실행 시간메모리
234709Charis02Port Facility (JOI17_port_facility)C++14
0 / 100
34 ms47480 KiB
#include<iostream> #include<stdio.h> #include<vector> #include<cmath> #include<queue> #include<string.h> #include<map> #include<set> #include<stack> #include<algorithm> #define ll long long #define pi pair < ll,ll > #define mp(a,b) make_pair(a,b) #define mid (low+high)/2 #define rep(i,a,b) for(int i = a;i < b;i++) #define N 2000004 #define INF 1e9+7 using namespace std; ll n,mod=1e9+7; pi ar[N]; ll seg[4*N]; bool vis[N]; ll col[N]; ll points[N]; vector < ll > graph[N]; void update(ll low,ll high,ll pos,ll slow,ll val) { if(low==high&&low==slow) { seg[pos]=val; return; } if(low>slow||high<slow) return; update(low,mid,pos*2+1,slow,val); update(mid+1,high,pos*2+2,slow,val); seg[pos]=max(seg[pos*2+1],seg[pos*2+2]); return; } ll query(ll low,ll high,ll pos,ll slow,ll shigh) { if(low>=slow&&high<=shigh) return seg[pos]; if(low>shigh||high<slow) return 0; return max(query(low,mid,pos*2+1,slow,shigh),query(mid+1,high,pos*2+2,slow,shigh)); } void dfs(ll cur,ll c) { if(vis[cur]) return; col[cur] = c; vis[cur]=true; rep(i,0,graph[cur].size()) dfs(graph[cur][i],!c); return; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; rep(i,0,n) { cin >> ar[i].first >> ar[i].second; } sort(ar,ar+n); rep(i,0,n) { points[ar[i].first]=i; points[ar[i].second]=i; ll q = query(0,2*n,0,ar[i].first,ar[i].second); if(q!=0) { q--; graph[q].push_back(i); graph[q].push_back(q); } update(0,2*n,0,ar[i].second,i+1); } ll ans = 1; rep(i,0,n) { if(!vis[i]) ans=(ans*2)%mod; dfs(i,0); } stack < ll > s[2]; rep(i,1,2*n+1) { ll ind = points[i]; if(ar[ind].first==i) { s[col[ind]].push(ind); } else { if(s[col[ind]].top() != ind) { ans=0; break; } else s[col[ind]].pop(); } } cout << ans << endl; return 0; }

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

port_facility.cpp: In function 'void dfs(long long int, long long int)':
port_facility.cpp:15:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
port_facility.cpp:60:9:
     rep(i,0,graph[cur].size())
         ~~~~~~~~~~~~~~~~~~~~~       
port_facility.cpp:60:5: note: in expansion of macro 'rep'
     rep(i,0,graph[cur].size())
     ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...