Submission #428552

#TimeUsernameProblemLanguageResultExecution timeMemory
428552mat_vPort Facility (JOI17_port_facility)C++14
100 / 100
2211 ms209696 KiB
#include <bits/stdc++.h> #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i)) #define N 1000005 #define pii pair<int,int> #define xx first #define yy second #define MOD 1000000007 #define pb push_back using namespace std; typedef long long ll; ll mul(ll x, ll y){ return (x*y)%MOD; } ll power(ll x, ll y){ if(y == 0)return 1; ll pola = power(x, y/2); pola = mul(pola, pola); if(y%2 == 1)pola = mul(pola, x); return pola; } int n; pii niz[2 * N]; int levo[N]; int desno[N]; pii par[N]; struct cvor{ int najm; int najv; int p1; int p2; }; cvor spoji(cvor a, cvor b){ cvor c = a; if(b.najm < c.najm){ c.najm = b.najm; c.p1 = b.p1; } if(b.najv > c.najv){ c.najv = b.najv; c.p2 = b.p2; } return c; } cvor seg[8 * N]; void init(int node, int l, int r){ if(l == r){ seg[node] = {niz[l].xx, niz[l].xx, niz[l].yy, niz[l].yy}; return; } int mid = (l + r) / 2; init(node * 2, l, mid); init(node * 2 + 1, mid + 1, r); seg[node] = spoji(seg[node * 2], seg[node * 2 + 1]); } cvor query(int node, int l, int r, int levo, int desno){ if(l > r || levo > desno || levo > r || l > desno)return {(int)1e9, 0, -1, -1}; if(l >= levo && r <= desno)return seg[node]; int mid = (l + r) / 2; return spoji(query(node*2,l,mid,levo,desno), query(node*2+1,mid+1,r,levo,desno)); } int br; int boja[N]; vector<int> graf[N]; void dfs(int x, int y){ boja[x] = y; for(auto c:graf[x]){ if(boja[c] == -1)dfs(c,y^1); else if(boja[c] == y){ cout << 0 << "\n"; exit(0); } } } int main() { ios_base::sync_with_stdio(false); cin >> n; ff(i,1,n){ int x,y; cin >> x >> y; par[i] = {x,y}; niz[x] = {y,i}; niz[y] = {x,i}; } init(1,1,2*n); ff(i,1,n){ if(par[i].xx + 1 == par[i].yy)continue; cvor sta = query(1,1,2*n,par[i].xx + 1,par[i].yy - 1); if(sta.najm < par[i].xx){ //levo[i] = sta.p1; graf[i].pb(sta.p1); graf[sta.p1].pb(i); } if(sta.najv > par[i].yy){ graf[i].pb(sta.p2); graf[sta.p2].pb(i); } } // cout << "\n"; // ff(i,1,n){ // cout << levo[i] << " " << desno[i] << "\n"; // } // cout << "\n\n"; ff(i,1,n)boja[i] = -1; ff(i,1,n){ if(boja[i] == -1){ br++; dfs(i,0); } } cout << power(2, br) << "\n"; return 0; }

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
port_facility.cpp:91:5: note: in expansion of macro 'ff'
   91 |     ff(i,1,n){
      |     ^~
port_facility.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
port_facility.cpp:101:5: note: in expansion of macro 'ff'
  101 |     ff(i,1,n){
      |     ^~
port_facility.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
port_facility.cpp:119:5: note: in expansion of macro 'ff'
  119 |     ff(i,1,n)boja[i] = -1;
      |     ^~
port_facility.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
port_facility.cpp:120:5: note: in expansion of macro 'ff'
  120 |     ff(i,1,n){
      |     ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...