제출 #167021

#제출 시각아이디문제언어결과실행 시간메모리
167021theStaticMindPort Facility (JOI17_port_facility)C++14
100 / 100
3280 ms132500 KiB
#include<bits/stdc++.h> #define mp make_pair #define pb push_back #define ii pair<int,int> #define all(x) (x).begin(),(x).end() #define INF 100000000000000000 #define modulo 1000000007 #define mod 998244353 #define int long long int using namespace std; vector<int>no(2000004); vector<pair<int,ii>> arr; int F(int x){ if(x==no[x])return x; return no[x]=F(no[x]); } bool merge(int x,int y){ x=F(x); y=F(y); if(x==y)return false; no[x]=y; return true; } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); // freopen("q.gir","r",stdin); // freopen("q.cik","w",stdout); int n,ans=1; for(int i=0;i<no.size();i++)no[i]=i; cin>>n; for(int i=1;i<=n;i++){ int a,b; cin>>a>>b; arr.pb({a,{b,i}}); } sort(all(arr)); set<ii>data; for(int i=0;i<arr.size();i++){ int x=arr[i].first,y=arr[i].second.first,id=arr[i].second.second; set<ii>::iterator ptr=data.upper_bound({y,0}); for(set<ii>::iterator itr=data.lower_bound({x,0});itr!=ptr;itr++){ merge(itr->second+n,id); merge(itr->second,id+n); if(F(itr->second)==F(prev(ptr)->second))break; } data.insert({y,id}); } for(int i=1;i<=n;i++){ if(F(i)==F(i+n))ans=0; if(F(i)==i)ans=ans*2%modulo; } cout<<ans; }

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

port_facility.cpp: In function 'int32_t main()':
port_facility.cpp:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<no.size();i++)no[i]=i;
                   ~^~~~~~~~~~
port_facility.cpp:39:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<arr.size();i++){
                   ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...