Submission #209811

#	Time	Username	Problem	Language	Result	Execution time	Memory
209811		stefdasca	Port Facility (JOI17_port_facility)	C++14	0 / 100	7 ms	376 KiB

port_facility

/*

        JOISC 17-port_facility

    Let's define a graph where each container is a vertex and we draw edges between two containers which can't be put in the same area.
Therefore, the answer will be 2^(number of connected components) or 0 if the graph isn't bipartite(this can be checked beforehand with some simulation).

    Since the number of edges can be really big, we need segment tree to reduce the number of edges we are going to use.

*/
#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9

// #define fisier 1

using namespace std;

typedef long long ll;

int n;
pair<int, int> bk[1000002];

void chk()
{
    vector<int> d[2];
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 0; j <= 1; ++j)
            while(!d[j].empty() && d[j].back() < bk[i].fi)
                d[j].pop_back();
        if(d[0].empty() && d[1].empty())
            d[0].pb(bk[i].se);
        else
            if(d[1].empty())
            {
                if(bk[i].se < d[0].back())
                    d[0].pb(bk[i].se);
                else
                    d[1].pb(bk[i].se);
            }
            else
                if(d[0].empty())
                {
                    if(bk[i].se < d[1].back())
                        d[1].pb(bk[i].se);
                    else
                        d[0].pb(bk[i].se);
                }
                else
                {
                    if(bk[i].se > max((int) d[0].back(), (int) d[1].back()))
                    {
                        cout << 0 << '\n';
                        exit(0);
                    }
                    if(d[0].back() < d[1].back())
                    {
                        if(bk[i].se < d[0].back())
                            d[0].pb(bk[i].se);
                        else
                            d[1].pb(bk[i].se);
                    }
                    else
                    {
                        if(bk[i].se < d[1].back())
                            d[1].pb(bk[i].se);
                        else
                            d[0].pb(bk[i].se);
                    }
                }
    }
}

int aint[4000002], aint2[4000002];
void build(int nod, int st, int dr)
{
    if(st == dr)
    {
        aint[nod] = st;
        return;
    }
    int mid = (st + dr) / 2;
    build(nod << 1, st, mid);
    build(nod << 1|1, mid+1, dr);
    if(bk[aint[nod << 1]].se > bk[aint[nod << 1|1]].se)
        aint[nod] = aint[nod << 1];
    else
        aint[nod] = aint[nod << 1|1];
}
void upd(int nod, int st, int dr, int poz)
{
    if(st == dr)
    {
        aint[nod] = 0;
        return;
    }
    int mid = (st + dr) / 2;
    if(poz <= mid)
        upd(nod << 1, st, mid, poz);
    else
        upd(nod << 1|1, mid+1, dr, poz);
    if(bk[aint[nod << 1]].se > bk[aint[nod << 1|1]].se)
        aint[nod] = aint[nod << 1];
    else
        aint[nod] = aint[nod << 1|1];
}
int query(int nod, int st, int dr, int L, int R)
{
    if(dr < L || st > R)
        return 0;
    if(L <= st && dr <= R)
        return aint[nod];
    int mid = (st + dr) / 2;
    int ans1 = query(nod << 1, st, mid, L, R);
    int ans2 = query(nod << 1|1, mid+1, dr, L, R);
    if(bk[ans1].se > bk[ans2].se)
        return ans1;
    else
        return ans2;
}

void build2(int nod, int st, int dr)
{
    if(st == dr)
    {
        aint[nod] = st;
        return;
    }
    int mid = (st + dr) / 2;
    build(nod << 1, st, mid);
    build(nod << 1|1, mid+1, dr);
    if(bk[aint[nod << 1]].fi < bk[aint[nod << 1|1]].fi)
        aint[nod] = aint[nod << 1];
    else
        aint[nod] = aint[nod << 1|1];
}
void upd2(int nod, int st, int dr, int poz)
{
    if(st == dr)
    {
        aint[nod] = 0;
        return;
    }
    int mid = (st + dr) / 2;
    if(poz <= mid)
        upd(nod << 1, st, mid, poz);
    else
        upd(nod << 1|1, mid+1, dr, poz);
    if(bk[aint[nod << 1]].fi < bk[aint[nod << 1|1]].fi)
        aint[nod] = aint[nod << 1];
    else
        aint[nod] = aint[nod << 1|1];
}
int query2(int nod, int st, int dr, int L, int R)
{
    if(dr < L || st > R)
        return 0;
    if(L <= st && dr <= R)
        return aint[nod];
    int mid = (st + dr) / 2;
    int ans1 = query2(nod << 1, st, mid, L, R);
    int ans2 = query2(nod << 1|1, mid+1, dr, L, R);
    if(bk[ans1].fi < bk[ans2].fi)
        return ans1;
    else
        return ans2;
}
bool viz[1000002];
int cb(int x)
{
    int st = 1;
    int dr = n;
    int ans = 0;
    while(st <= dr)
    {
        int mid = (st + dr) / 2;
        if(bk[mid].fi <= x)
            ans = mid, st = mid + 1;
        else
            dr = mid - 1;
    }
    return ans;
}
void dfs(int nod)
{
    viz[nod] = 1;
    upd(1, 1, n, nod);
    upd2(1, 1, n, nod);
    int maxpoz = cb(bk[nod].se);
    while(1)
    {
        int poz = 0;
        if(nod < maxpoz)
            poz = query2(1, 1, n, nod+1, maxpoz);
        if(bk[poz].fi < bk[nod].fi)
            dfs(poz);
        else
            break;
    }
    while(1)
    {
        int poz = 0;
        if(maxpoz > nod)
            poz = query(1, 1, n, nod+1, maxpoz);
        if(bk[poz].se > bk[nod].se)
            dfs(poz);
        else
            break;
    }
}
int main()
{

    #ifdef fisier
        ifstream f("input.in");
        ofstream g("output.out");
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> bk[i].fi >> bk[i].se;
    sort(bk + 1, bk + n + 1);
    bk[0].fi = (1<<30);
    bk[0].se = -(1<<30);
    chk();
    build(1, 1, n);
    build2(1, 1, n);
    int ans = 1;
    for(int i = 1; i <= n; ++i)
        if(!viz[i])
        {
            ans = (ans * 2) % mod;
            dfs(i);
        }
    cout << ans << '\n';
    return 0;
}

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