제출 #428552

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
428552		mat_v	Port Facility (JOI17_port_facility)	C++14	100 / 100	2211 ms	209696 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
#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;
}

컴파일 시 표준 에러 (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){
      |     ^~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 56 / 56
• Subtask 4: 22 / 22