Submission #234727

#	Time	Username	Problem	Language	Result	Execution time	Memory
234727		Charis02	Port Facility (JOI17_port_facility)	C++14	100 / 100	4008 ms	238676 KiB

port_facility

#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#include<stack>
#include<algorithm>
#define ll long long
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define mid (low+high)/2
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 2000004
#define INF 1e9+7

using namespace std;

ll n,mod=1e9+7;
pi ar[N];
ll seg[4*N][2];
bool vis[N];
ll col[N];
ll points[N];
vector < ll > graph[N];

void init(ll low,ll high,ll pos)
{
    seg[pos][0]=2*n+1;
    seg[pos][1]=0;
    if(low==high)
        return;
    init(low,mid,pos*2+1);
    init(mid+1,high,pos*2+2);
    return;
}

void update(ll low,ll high,ll pos,ll slow,ll val,ll id)
{
    if(low==high&&low==slow)
    {
        seg[pos][id]=val;
        return;
    }
    if(low>slow||high<slow)
        return;
    update(low,mid,pos*2+1,slow,val,id);
    update(mid+1,high,pos*2+2,slow,val,id);
    seg[pos][0]=min(seg[pos*2+1][0],seg[pos*2+2][0]);
    seg[pos][1]=max(seg[pos*2+1][1],seg[pos*2+2][1]);
    return;
}

ll query(ll low,ll high,ll pos,ll slow,ll shigh,ll id)
{
    //cout << low << " " << high << " " << pos << " " << slow<< " " << shigh << " " << id << " " << seg[pos][id] << endl;
    if(low>=slow&&high<=shigh)
        return seg[pos][id];
    if(low>shigh||high<slow)
    {
        if(id==1)
            return 0;
        return 2*n+1;
    }
    if(id==1)
        return max(query(low,mid,pos*2+1,slow,shigh,id),query(mid+1,high,pos*2+2,slow,shigh,id));
    else
        return min(query(low,mid,pos*2+1,slow,shigh,id),query(mid+1,high,pos*2+2,slow,shigh,id));
}

void dfs(ll cur,ll c)
{
    if(vis[cur])
        return;
    col[cur] = c;
    vis[cur]=true;

    update(0,2*n,0,ar[cur].second,2*n+1,0);
    update(0,2*n,0,ar[cur].first,0,1);

   // cout << "here " << cur << " " << c << endl;

    // find left intersections

    ll q = query(0,2*n,0,ar[cur].first,ar[cur].second,0);

    while(q < ar[cur].first)
    {
        q=points[q];
        dfs(q,!c);
        q = query(0,2*n,0,ar[cur].first,ar[cur].second,0);
    }

    // find right intersections

    q = query(0,2*n,0,ar[cur].first,ar[cur].second,1);

    while(q > ar[cur].second)
    {
        q=points[q];
        dfs(q,!c);
        q = query(0,2*n,0,ar[cur].first,ar[cur].second,1);
    }

  //  cout << "out " << cur << " " << c << endl;

    return;
}

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

    cin >> n;

    rep(i,0,n)
    {
        cin >> ar[i].first >> ar[i].second;
    }

    init(0,2*n,0);

    rep(i,0,n)
    {
        points[ar[i].first]=points[ar[i].second]=i;
        update(0,2*n,0,ar[i].second,ar[i].first,0);
        update(0,2*n,0,ar[i].first,ar[i].second,1);
    }

    ll ans = 1;
    rep(i,0,n)
    {
        if(!vis[i])
            ans=(ans*2)%mod;
        dfs(i,0);
    }

    stack < ll > s[2];

    rep(i,1,2*n+1)
    {
        ll ind = points[i];
        if(ar[ind].first==i)
        {
            s[col[ind]].push(ind);
        }
        else
        {
            if(s[col[ind]].top() != ind)
            {
                ans=0;
                break;
            }
            else
                s[col[ind]].pop();
        }
    }

    cout << ans << endl;

    return 0;
}

/*
4
1 5
2 6
3 4
7 8
*/

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