Submission #529179

#	Time	Username	Problem	Language	Result	Execution time	Memory
529179		radal	Port Facility (JOI17_port_facility)	C++14	100 / 100	1273 ms	242436 KiB

port_facility

#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 1e6+20,mod = 1e9+7,inf = 1e9+10;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}

inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    }
    return z;
}
pll p[N];
int seg[N*4],a[N*2],n,cmp[N],col[N];
set<pll> en[N];
vector<int> adj[N];
void upd(int l,int r,int p,int x,int v = 1){
    if (r-l == 1){
        seg[v] = x;
        return;
    }
    int m = (l+r) >> 1,u = (v << 1);
    if (p < m) upd(l,m,p,x,u);
    else upd(m,r,p,x,u|1);
    seg[v] = seg[u]+seg[u|1];
}
bool dfs(int v,int t){
    if (col[v])
        return (col[v] == t);
    col[v] = t;
    for (int u : adj[v]) if (!dfs(u,3-t)) return 0;
    return 1;
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n;
    rep(i,1,n+1)
        cin >> p[i].X >> p[i].Y;
    sort(p+1,p+n+1);
    int nn = 2*n;
    rep(i,1,n+1) a[p[i].X] = a[p[i].Y] = i;
    int mx = 0;
    bool f = 1;
    rep(i,1,nn+1){
        if (p[a[i]].X == i){
            if (mx > p[a[i]].Y) continue;
            mx = p[a[i]].Y;
            upd(0,n+1,a[i],1);
            if (seg[1] > 2){
                f = 0;
                break;
            }
        }
        else upd(0,n+1,a[i],0);
    }
    if (!f){
        cout << 0;
        return 0;
    }
    int cnt = 0;
    set<pair<pll,int> > st;
    rep(i,1,n+1){
        pll g = {p[i].Y,p[i].Y};
        int y = i;
        cmp[i] = i;
        en[y].insert({p[i].Y,i});
        vector<pair<pll,int>> er;
        for(pair<pll,int> x : st){
            if (x.X.X < p[i].X){
                er.pb(x);
                cnt++;
                continue;
            }
            if (x.X.Y > g.X)
                break;
            auto it = en[x.Y].lower_bound(make_pair(p[i].X,0));
            pll z = *(it);
            if (it == en[x.Y].end() || z.X >= p[i].Y) continue;
            adj[z.Y].pb(i);
            adj[i].pb(z.Y);
            if (en[x.Y].upper_bound(z) != en[x.Y].end()){
                pll w = *(en[x.Y].upper_bound(z));
                if (w.X < p[i].Y){
                    adj[w.Y].pb(i);
                    adj[i].pb(w.Y);
                }
            }

            er.pb(x);
            g = {max(g.X,x.X.X),min(g.Y,x.X.Y)};
            if (en[y].size() > en[x.Y].size()) swap(y,x.Y);
            for (pll d : en[y]){
                en[x.Y].insert(d);
                cmp[d.Y] = x.Y;
            }
            en[y].clear();
            y = x.Y;
        }
        for(pair<pll,int> x : er) st.erase(x);
        st.insert({g,y});
    }
    rep(i,1,n+1){
        if (col[i]) continue;
        f &= dfs(i,1);
    }
    cout << ((!f) ? 0 : poww(2,st.size()+cnt));
}

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