제출 #136670

#제출 시각아이디문제언어결과실행 시간메모리
136670AlliancePort Facility (JOI17_port_facility)C++14
22 / 100
6145 ms940568 KiB
// In the Name of Allah #include<bits/stdc++.h> #define double long double typedef long long ll; const ll MAX_N = 2e6+100; const ll MOD = 1e9+7; using namespace std; vector<int> seg[MAX_N*3][2]; pair<int,int> lr[MAX_N]; int a[MAX_N]; int b[MAX_N]; int p[MAX_N]; vector<int> g[MAX_N]; vector<int> vc; int mark[MAX_N]; int cl[MAX_N]; int n,cnt; void no(){ cout << 0; exit(0); } void dfs(int v){ mark[v]++; for(auto x:g[v]){ if (mark[x]){ if (cl[x]==cl[v]) no(); } else{ cl[x] = 3-cl[v]; dfs(x); } } } void build(int k,int l,int r){ if (l==r){ if (a[l]) seg[k][0].push_back(a[l]); if (b[l]) seg[k][1].push_back(b[l]); return; } int mid = (l+r)/2; build(k*2,l,mid); build(k*2+1,mid+1,r); for(int i = 0;i<2;++i){ int lc = k*2; int rc = lc+1; seg[k][i].resize(seg[lc][i].size()+seg[rc][i].size()); merge(seg[lc][i].begin(),seg[lc][i].end(),seg[rc][i].begin(),seg[rc][i].end(),seg[k][i].begin()); } } void ask(int l,int r,int a,int b,int k,int fl){ if (r<a or b<l) return; if (a<=l and r<=b){ if (fl==0){ for(auto x:seg[k][0]){ if (x>=a) return; vc.push_back(x); } } else { for(int i = seg[k][1].size()-1;i>=0;--i){ int x = seg[k][1][i]; if (x<=b) return; vc.push_back(x); } } return; } int mid = (l+r)/2; ask(l,mid,a,b,k*2,fl); ask(mid+1,r,a,b,k*2+1,fl); } int main() { cin >> n; for(int i = 1;i<=n;++i) scanf("%d%d",&lr[i].first,&lr[i].second); for(int i = 1;i<=n;++i){ b[lr[i].first] = lr[i].second; a[lr[i].second] = lr[i].first; p[lr[i].second] = p[lr[i].first] = i; } build(1,1,2*n); for(int i = 1;i<=n;++i){ vc.clear(); ask(1,2*n,lr[i].first,lr[i].second,1,0); if (vc.size()){ sort(vc.begin(),vc.end()); for(int j = 0;j<vc.size()-1;j++) { int x = vc[j]; int y = vc[j+1]; if (b[y]>b[x]) no(); } for(auto x:vc) g[i].push_back(p[x]); } vc.clear(); ask(1,2*n,lr[i].first,lr[i].second,1,1); if (vc.size()){ sort(vc.begin(),vc.end()); for(int j = 0;j<vc.size()-1;j++){ int x = vc[j]; int y = vc[j+1]; if (a[y]>a[x]) no(); } } for(auto x:vc) g[i].push_back(p[x]); } for(int i = 1;i<=n;++i){ if (mark[i]) continue; cnt++; dfs(i); } ll ans = 1; while(cnt--) ans *= 2,ans %= MOD; cout << ans; return 0; }

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

port_facility.cpp: In function 'int main()':
port_facility.cpp:101:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0;j<vc.size()-1;j++)
                           ~^~~~~~~~~~~~
port_facility.cpp:115:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0;j<vc.size()-1;j++){
                           ~^~~~~~~~~~~~
port_facility.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&lr[i].first,&lr[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...