제출 #70721

#제출 시각아이디문제언어결과실행 시간메모리
70721yogahmadPort Facility (JOI17_port_facility)C++14
78 / 100
6040 ms588856 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define fbo find_by_order #define ook order_of_key #define f first #define s second #define pb push_back #define reset(a,b) memset(a,b,sizeof a); #define MOD 1000000007 #define MID (l+r)/2 #define ALL(x) x.begin(),x.end() #define debug(x) cout<<#x<<" = "<<(x)<<endl #define mx 2000003 #define pc(x) putchar_unlocked(x); typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> pbds; vector<int>ve[mx*4]; pair<int,int>a[mx]; int n,par[mx]; int find(int x){ // debug(x); if(x==par[x])return x; return par[x]=find(par[x]); } void gabung(int idx,int l,int r,int fl,int fr,int val){ if(fl>r || fr<l)return; if(ve[idx].size()==0)return; if(fl<=l && r<=fr){ // debug(val); for(int i:ve[idx]){ int j=i; if(j<=n)j+=n; else j-=n; i=find(i); // debug(i); j=find(j); par[i]=find(val+n); par[j]=find(val); } ve[idx].clear(); ve[idx].pb(find(val+n)); return; } if(!(fl>MID || fr<l))gabung(idx*2,l,MID,fl,fr,val); if(!(fl>r || fr<MID+1))gabung(idx*2+1,MID+1,r,fl,fr,val); } void upd(int idx,int l,int r,int in,int val){ ve[idx].pb(find(val)); if(l==r)return; if(in<=MID)upd(2*idx,l,MID,in,val); else upd(2*idx+1,MID+1,r,in,val); } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d%d",&a[i].f,&a[i].s); sort(a+1,a+n+1); for(int i=1;i<=n*2;i++){ par[i]=i; } for(int i=1;i<=n;i++){ gabung(1,1,n*2,a[i].f,a[i].s,i); upd(1,1,n*2,a[i].s,i); } for(int i=1;i<=n;i++){ // debug(i); int x=find(i); int y=find(i+n); if(x==y){ // debug(i); cout<<0<<endl; return 0; } } set<int>isi; for(int i=1;i<=n*2;i++){ isi.insert(find(i)); } int tot=isi.size(); assert(tot%2==0); tot/=2; long long jaw=1; for(int i=1;i<=tot;i++){ jaw=jaw*2%MOD; } cout<<jaw<<endl; }

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

port_facility.cpp: In function 'int main()':
port_facility.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
port_facility.cpp:62:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++)scanf("%d%d",&a[i].f,&a[i].s);
                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...