제출 #892622

#제출 시각아이디문제언어결과실행 시간메모리
892622ReLicePort Facility (JOI17_port_facility)C++14
10 / 100
146 ms291152 KiB
#include <bits/stdc++.h> #define ll int #define str string #define ins insert #define ld long double #define pb push_back #define pf push_front #define pof pop_front() #define pob pop_back() #define lb lower_bound #define ub upper_bound #define endl "\n" #define fr first #define sc second #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define sz size() #define bc back() //#define ar array #define vll vector<ll> using namespace std;/* #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds;*/ template <class _T> bool chmin(_T &x, const _T &y){ if(x>y){ x=y; return true; } return false; } template <class _T> bool chmax(_T &x, const _T &y){ bool flag=false; if (x<y){ x=y;flag|=true; } return flag; } //#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update> void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);} void start(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } const ll inf=2e18+7; const ll mod=1e9+7; const ll N=2e6+7; const ld eps=1e-9; vector<vector<pair<ll,ll>>> t(N*4),ar(N); vector<vll> g(N); ll comp[N]; ll val[N]; void build(ll v,ll tl,ll tr){ if(tl==tr){ for(auto i : ar[tl])t[v].pb(i); return; } ll tm=(tl+tr)/2; build(v*2,tl,tm); build(v*2+1,tm+1,tr); for(auto i : t[v*2])t[v].pb(i); for(auto i : t[v*2+1])t[v].pb(i); } vector<pair<ll,ll> > get(ll v,ll tl,ll tr,ll l,ll r){ if(tl>r || tr<l)return {}; if(l<=tl && tr<=r)return t[v]; ll tm=(tl+tr)/2; vector<pair<ll,ll>> vv; for(auto i : get(v*2,tl,tm,l,r))vv.pb(i); for(auto i : get(v*2+1,tm+1,tr,l,r))vv.pb(i); return vv; } void dfs(ll v,ll c){ comp[v]=c; for(auto i : g[v]){ if(comp[i])continue; dfs(i,c); } } void solve(){ ll i; ll n; ll a,b; cin>>n; vector<vll> del(n*2+5); vector<vector<pair<ll,ll>>> cur(n*2+5); for(i=1;i<=n;i++){ cin>>a>>b; del[b].pb(i); ar[b].pb({a,i}); cur[a].pb({b,i}); } build(1,1,n*2); for(i=1;i<=2*n;i++){ for(auto j : cur[i]){ vector<pair<ll,ll>> v=get(1,1,n*2,i,j.fr); sort(all(v)); for(auto q : v){ if(q.fr>=i)break; g[q.sc].pb(j.sc); g[j.sc].pb(q.sc); val[j.sc]=max(val[q.sc]+1,val[j.sc]); } if(val[j.sc]>1){ cout<<0<<endl; return; } } for(auto j : del[i]){ for(auto to : g[j]){ val[to]--; } } } ll c=0; for(i=1;i<=n;i++){ if(comp[i]==0)dfs(i,++c); } ll x=1; for(i=1;i<=c;i++){ x*=2; x%=mod; } cout<<x<<endl; } signed main(){ start(); ll t=1; //cin>>t; while(t--) solve(); return 0; } /* 1 6 5 4 3 2 1 0 */

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

port_facility.cpp:48:18: warning: overflow in conversion from 'double' to 'int' changes value from '2.0e+18' to '2147483647' [-Woverflow]
   48 | const ll inf=2e18+7;
      |              ~~~~^~
port_facility.cpp: In function 'void fre(std::string)':
port_facility.cpp:42:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
port_facility.cpp:42:64: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...