Submission #130607

#	Time	Username	Problem	Language	Result	Execution time	Memory
130607		doowey	Port Facility (JOI17_port_facility)	C++14	100 / 100	3986 ms	230264 KiB

port_facility

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ld, ld> pdd;
 
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 
const int N = (int)1e6 + 2;
const int inf = (int)1e8;
const int MOD = (int)1e9 + 7;
pii tr[2][N * 4 + 51];

int k;
void update(int tv, int ps, pii nw){
    ps += k;
    tr[tv][ps] = nw;
    ps /= 2;
    while(ps > 0){
        if(tv == 0) tr[tv][ps] = min(tr[tv][ps * 2], tr[tv][ps * 2 + 1]);
        if(tv == 1) tr[tv][ps] = max(tr[tv][ps * 2], tr[tv][ps * 2 + 1]);
        ps /= 2;
    }
}

pii query(int tv, int cl, int cr){
    cl += k;
    cr += k;
    pii cur = mp(-inf, -1);
    if(tv == 0)
        cur.fi = inf;
    while(cl <= cr){
        if(cl % 2 == 1){
            if(tv==0) cur = min(cur, tr[tv][cl]);
            else cur = max(cur, tr[tv][cl]);
            cl ++ ;
        }
        if(cr % 2 == 0){
            if(tv==0) cur = min(cur, tr[tv][cr]);
            else cur = max(cur, tr[tv][cr]);
            cr -- ;
        }
        cl /= 2;
        cr /= 2;
    }
    return cur;
}

pii cl[N * 2];
pii cr[N * 2];
pii q[N];

int bit[N];

void dfs(int u, int b){
    bit[u] = b;
    update(0, q[u].se, mp(inf, -1));
    update(1, q[u].fi, mp(-inf, -1));   
    int l = q[u].fi, r = q[u].se;
    pii cur;
    while(1){
        cur = query(0, l, r);
        if(cur.se == -1 || cur.fi >= l)
            break;
        dfs(cur.se, !b);
    }
    while(1){
        cur = query(1, l, r);
        if(cur.se == -1 || cur.fi <= r){
            break;
        }
        dfs(cur.se, !b);
    }
}

int sum[2][N * 4];

void upd(int bt, int id, int x){
    id += k;
    while(id > 0){
        sum[bt][id] += x;
        id /= 2;
    }
}

int qry(int bt, int l, int r){    
    l += k;
    r += k;
    int res = 0;
    while(l <= r){
        if(l % 2 == 1) res += sum[bt][l ++ ];
        if(r % 2 == 0) res += sum[bt][r -- ];
        l /= 2;
        r /= 2;
    }
    return res;
}

int main(){
    fastIO;
    for(int i = 0 ; i < N * 2; i ++ )
        cl[i] = mp(inf, -1), cr[i] = mp(-inf, -1);
    int n;
    cin >> n;
    k = n * 2;
    for(int i = 0 ; i < k ; i ++ ){
        update(0, i, mp(+inf, -1));
        update(1, i, mp(-inf, -1));
    }
    for(int i = 0 ; i < n; i ++ ){
        cin >> q[i].fi >> q[i].se;
        q[i].fi -- ;
        q[i].se -- ;
        cl[q[i].se] = mp(q[i].fi, i);
        cr[q[i].fi] = mp(q[i].se, i);
        bit[i] = -1;
        update(0, q[i].se, cl[q[i].se]);
        update(1, q[i].fi, cr[q[i].fi]);
    }
    int ans = 1;
    for(int i = 0 ; i < k ; i ++ ){
        if(bit[i] == -1){
            dfs(i, 0);
            ans = (ans * 2ll) % MOD;
        }
    }
    for(int i = 0 ; i < n; i ++ ){
        upd(bit[i], q[i].se, +1);
    }
    for(int i = k - 1; i >= 0 ; i -- ){
        if(cr[i].se != -1){
            upd(bit[cr[i].se], cr[i].fi, -1);
            if(qry(bit[cr[i].se], i, cr[i].fi) > 0){
                ans = 0;
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

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