Submission #427295

#	Time	Username	Problem	Language	Result	Execution time	Memory
427295		lyc	Port Facility (JOI17_port_facility)	C++14	10 / 100	12 ms	904 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef pair<int,int> ii;

const int mxN = 1e6+5;
const int mod = 1e9+7;

struct Itv {
    int s, e, i;
};

int N;
vector<Itv> C;

struct UFDS {
    vector<int> p, s;
    int comp;

    void init(int n) {
        comp = n;
        p.assign(n,0);
        iota(ALL(p),0);
        s.assign(n,1);
    }

    int finds(int i) {
        return (p[i] == i) ? i : (p[i] = finds(p[i]));
    }

    bool sames(int i, int j) {
        return finds(i) == finds(j);
    }

    bool unions(int i, int j) {
        int x = finds(i), y = finds(j);
        if (x == y) return 0;
        --comp;
        if (s[x] < s[y]) swap(x,y);
        s[x] += s[y];
        p[y] = x;
        return 1;
    }
} ufds;

struct node {
    int s, e, m;
    ii vmin, vmax;
    node *l, *r;

    node(int s, int e): s(s), e(e), m((s+e)/2) {
        if (s != e) {
            l = new node(s,m);
            r = new node(m+1,e);
        }
    }

    void update(int a, ii b) {
        if (s == e) {
            vmin = vmax = b;
            return;
        } else if (a <= m) l->update(a,b);
        else r->update(a,b);
        vmin = min(l->vmin,r->vmin);
        vmax = max(l->vmax,r->vmax);
    }

    ii qmin(int a, int b) {
        if (s == a && e == b) return vmin;
        if (b <= m) return l->qmin(a,b);
        if (a > m) return r->qmin(a,b);
        return min(l->qmin(a,m), r->qmin(m+1,b));
    }

    ii qmax(int a, int b) {
        if (s == a && e ==b ) return vmax;
        if (b <= m) return l->qmax(a,b);
        if (a > m) return r->qmax(a,b);
        return max(l->qmax(a,m), r->qmax(m+1,b));
    }

} *root;

int ls[mxN], rs[mxN];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> N;
    FOR(i,0,N-1){
        int a, b; cin >> a >> b;
        C.push_back({a,b,i});
    }

    ufds.init(N);
    root = new node(1,2*N);

    sort(ALL(C),[](Itv a, Itv b){ return a.e < b.e; });
    FOR(i,1,2*N) root->update(i, ii(1e9,-1));
    for (auto& x : C) {
        int lo = x.s-1, hi = x.e;
        while (hi-lo > 1) {
            int mid = (lo+hi)/2;
            auto r = root->qmin(mid,x.e);
            if (r.first < x.s) lo = mid;
            else hi = mid;
        }
        if (lo < x.s) ls[x.i] = -1;
        else {
            auto r = root->qmin(lo,x.e);
            ls[x.i] = lo;
            //TRACE(x.i _ r.second);
            ufds.unions(x.i, r.second);
        }
        root->update(x.e, ii(x.s, x.i));
    }

    sort(ALL(C),[](Itv a, Itv b){ return a.s > b.s; });
    FOR(i,1,2*N) root->update(i, ii(-1e9,1));
    for (auto& x : C) {
        int lo = x.s, hi = x.e+1;
        while (hi-lo > 1) {
            int mid = (lo+hi)/2;
            auto r = root->qmax(x.s,mid);
            if (r.first > x.e) hi = mid;
            else lo = mid;
        }
        if (hi > x.e) rs[x.i] = -1;
        else {
            auto r = root->qmax(x.s,hi);
            rs[x.i] = hi;
            //TRACE(x.i _ r.second);
            ufds.unions(x.i, r.second);
        }
        root->update(x.s, ii(x.e, x.i));
    }

    FOR(i,0,N-1){
        if (ls[i] != -1 && rs[i] != -1 && ls[i] > rs[i]) {
            cout << 0 << '\n';
            return 0;
        }
    }

    ll ans = 1;
    FOR(i,1,ufds.comp) ans = ans*2 % mod;

    cout << ans << '\n';
}

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