Submission #209809

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

port_facility

#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];
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;
}
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);
    while(1)
    {
        int poz = 0;
        if(nod != 1)
            poz = query(1, 1, n, 1, nod-1);
        if(bk[poz].se > bk[nod].fi)
            dfs(poz);
        else
            break;
    }
    while(1)
    {
        int poz = 0;
        if(cb(bk[nod].se) > nod)
            poz = query(1, 1, n, nod+1, cb(bk[nod].se));
        else
            poz = 0;
        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);
    chk();
    build(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