Submission #428529

#	Time	Username	Problem	Language	Result	Execution time	Memory
428529		mat_v	Port Facility (JOI17_port_facility)	C++14	Compilation error	0 ms	0 KiB

port_facility

#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

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 {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];

void dfs(int x, int y){
    boja[x] = y;
    if(levo[x]){
        if(boja[levo[x]] >= 0){
            if(boja[levo[x]] == y){
                cout << 0 << "\n";
                exit(0);
            }
        }
        else{
            dfs(levo[x], y^1);
        }
    }
    if(desno[x]){
        if(boja[desno[x]] >= 0){
            if(boja[desno[x]] == y){
                cout << 0 << "\n";
                exit(0);
            }
        }
        else{
            dfs(desno[x], y^1);
        }
    }
}

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;
        if(sta.najv > par[i].yy)desno[i] = sta.p2;
    }

    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 'cvor query(int, int, int, int, int)':
port_facility.cpp:64:77: error: narrowing conversion of '1.0e+9' from 'double' to 'int' [-Wnarrowing]
   64 |     if(l > r || levo > desno || levo > r || l > desno)return {1e9, 0, -1, -1};
      |                                                                             ^
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:104:5: note: in expansion of macro 'ff'
  104 |     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:114:5: note: in expansion of macro 'ff'
  114 |     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:121:5: note: in expansion of macro 'ff'
  121 |     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:122:5: note: in expansion of macro 'ff'
  122 |     ff(i,1,n){
      |     ^~