Submission #167069

#	Time	Username	Problem	Language	Result	Execution time	Memory
167069		Atill83	Port Facility (JOI17_port_facility)	C++14	100 / 100	4539 ms	144580 KiB

port_facility

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 2e6+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n;
int t[4*MAXN][2];
int id[MAXN];
int yer[MAXN];
int sag[MAXN], sol[MAXN];
void build(int v, int tl, int tr){
    if(tl == tr){
        t[v][0] = t[v][1] = -1e9;
    }else{
        int tm = (tl + tr) / 2;
        build(2*v, tl, tm);
        build(2*v + 1, tm + 1, tr);
        t[v][0] = t[v][1] = -1e9;
    }
}

void upd(int v, int tl, int tr, int pos, int dis, int val){
    if(tl == tr){
        t[v][dis] = val;
    }else{
        int tm = (tl + tr) / 2;
        if(pos <= tm)
            upd(2*v, tl, tm, pos, dis, val);
        else upd(2*v + 1 , tm + 1, tr, pos, dis, val);
        t[v][dis] = max(t[2*v][dis], t[2*v + 1][dis]);
    }
}

int get(int v, int tl, int tr, int l, int r, int dis){
    if(l > r){
        return -1e9;
    }else if(tl == l && tr == r){
        return t[v][dis];
    }else{
        int tm = (tl + tr) / 2;
        ll ans1 = get(2*v, tl, tm, l, min(tm, r), dis);
        ll ans2 = get(2*v + 1 ,tm + 1, tr, max(tm + 1 ,l), r, dis);
        return max(ans1, ans2);
    }
}

int cnt = 0;
void dfs(int ind, int angi){
    //if(ind == 0) return;
    //cout<<ind<<" "<<angi<<endl;
    //if(cnt >= 100) return;
    //cnt++;

    yer[ind] = angi;
    while(true){
        int t = get(1, 1, 2*n, sol[ind] + 1, sag[ind] - 1, 0);
        //cout<<t<<endl;
        if(t < sag[ind]){
            break;
        }
        upd(1, 1, 2*n, sol[id[t]], 0, -1e9);
        upd(1, 1, 2*n, t, 1, -1e9);
        //cout<<id[t]<<endl;
        dfs(id[t], 3 - angi);
    }
    while(true){
        int t = -get(1, 1, 2*n, sol[ind] + 1, sag[ind] - 1, 1);
        //cout<<t<<endl;
        //return;
        if(t > sol[ind]){
            break;
        }
        upd(1, 1, 2*n, t, 0, -1e9);
        upd(1, 1, 2*n, sag[id[t]], 1, -1e9);
        dfs(id[t], 3 - angi);
    }
    
}

bool check(vector<pii> &ali){
    stack<pii> st;

    for(int i = 0; i < (int)ali.size(); i++){
        while(!st.empty() && st.top().ss < ali[i].ff){
            st.pop();
        }
        if(!st.empty() && ali[i].ff < st.top().ss && ali[i].ss > st.top().ss){
            return 0;
        }
        st.push(ali[i]);
    }
    return 1;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("../IO/int.txt","r",stdin);
        freopen("../IO/out.txt","w",stdout);
    #endif

    cin>>n;
    build(1, 1, 2*n);
    for(int i = 1; i <= n; i++){
        int l, r;
        cin>>l>>r;
        id[l] = i;
        id[r] = i;
        sag[i] = r;
        sol[i] = l;
        upd(1, 1, 2*n, l, 0, r);
        upd(1, 1, 2*n, r, 1, -l);
    }
    ll ans = 1;
    vector<pii> a1, a2;
    for(int i = 1; i <= n; i++){
        if(!yer[i]){
            upd(1, 1, 2*n, sol[i], 0, -1e9);
            upd(1, 1, 2*n, sag[i], 1, -1e9);
            dfs(i, 1);
            ans *= 2;
            ans %= mod;
        }
        if(yer[i] == 1){
            a1.push_back({sol[i], sag[i]});
        }else{
            a2.push_back({sol[i], sag[i]});
        }
    }
    sort(a1.begin(), a1.end());
    sort(a2.begin(), a2.end());
    if(check(a1) && check(a2))
        cout<<ans<<endl;
    else cout<<0<<endl;
    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

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