Submission #892636

#TimeUsernameProblemLanguageResultExecution timeMemory
892636ReLicePort Facility (JOI17_port_facility)C++17
0 / 100
61 ms282192 KiB
#include <bits/stdc++.h> #define ll long long #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; 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); } } bool flag[N]; void solve(){ ll i; ll n; ll a,b; cin>>n; vector<vector<pair<ll,ll>>> cur(n*2+5); vector<pair<ll,ll>> v(n+4); for(i=1;i<=n;i++) cin>>v[i].fr>>v[i].sc; ll mx=0; sort(all(v)); for(i=1;i<=n;i++){ if(mx>=v[i].sc)flag[i]=true; mx=max(mx,v[i].sc); } for(i=1;i<=n;i++){ if(flag[i])continue; a=v[i].fr; b=v[i].sc; 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 : ar[i]){ for(auto to : g[j.sc]){ 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; } /* 35 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 */

Compilation message (stderr)

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...