Submission #46422

#	Time	Username	Problem	Language	Result	Execution time	Memory
46422		SpaimaCarpatilor	Port Facility (JOI17_port_facility)	C++17	100 / 100	3896 ms	656108 KiB

port_facility

#include<bits/stdc++.h>

using namespace std;

const int NMAX = 1000009;
int N, M, a[NMAX], b[NMAX], p[2 * NMAX], pos[2 * NMAX], ap[NMAX];
const int mod = 1e9 + 7;

int ansMi, ansMa, hansMi, hansMa, mi[5 * NMAX], ma[5 * NMAX], hmi[5 * NMAX], hma[5 * NMAX];

void refresh (int nod, int f1, int f2)
{
    mi[nod] = min (mi[f1], mi[f2]);
    ma[nod] = max (ma[f1], ma[f2]);
    hmi[nod] = (mi[nod] == mi[f1] ? hmi[f1] : hmi[f2]);
    hma[nod] = (ma[nod] == ma[f1] ? hma[f1] : hma[f2]);
}

void build (int nod, int st, int dr)
{
    if (st == dr)
    {
        if (p[st] == 0) mi[nod] = 4 * N, ma[nod] = 0;
        else mi[nod] = ma[nod] = p[st];
        hmi[nod] = hma[nod] = st;
        return ;
    }
    int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
    build (f1, st, mij);
    build (f2, mij + 1, dr);
    refresh (nod, f1, f2);
}

void query (int nod, int st, int dr, int x, int y)
{
    if (x > y) return ;
    if (x <= st && dr <= y)
    {
        if (mi[nod] < ansMi)
            ansMi = mi[nod], hansMi = hmi[nod];
        if (ma[nod] > ansMa)
            ansMa = ma[nod], hansMa = hma[nod];
        return ;
    }
    int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
    if (x <= mij) query (f1, st, mij, x, y);
    if (mij < y) query (f2, mij + 1, dr, x, y);
}

void delPos (int nod, int st, int dr, int pos)
{
    if (st == dr)
    {
        mi[nod] = 4 * N, ma[nod] = 0;
        return ;
    }
    int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
    if (pos <= mij) delPos (f1, st, mij, pos);
    else delPos (f2, mij + 1, dr, pos);
    refresh (nod, f1, f2);
}

void delVal (int x)
{
    delPos (1, 1, 2 * N, a[x]);
    delPos (1, 1, 2 * N, b[x]);
}

void dfs (int nod, int c)
{
    if (ap[nod] != 0 && ap[nod] != c)
    {
        printf ("0\n");
        exit (0);
    }
    if (ap[nod] != 0) return ;
    ap[nod] = c, delVal (nod);
    while (1)
    {
        ansMi = 4 * N, ansMa = 0, query (1, 1, 2 * N, a[nod] + 1, b[nod] - 1);
        if (ansMi > a[nod] && ansMa < b[nod]) break;
        int toDel = 0;
        if (ansMi <= a[nod]) toDel = pos[hansMi];
        else toDel = pos[hansMa];
        dfs (toDel, 3 - c);
    }
}

void check (vector < int > &ids)
{
    for (int i=1; i<=2 * N; i++)
        p[i] = 0;
    for (auto it : ids)
        p[a[it]] = b[it], p[b[it]] = a[it];
    build (1, 1, 2 * N);
    for (auto i : ids)
    {
        ansMi = 4 * N, ansMa = 0, query (1, 1, 2 * N, a[i] + 1, b[i] - 1);
        if (ansMi < a[i] || ansMa > b[i])
        {
            printf ("0\n");
            exit (0);
        }
    }
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d", &N);
for (int i=1; i<=N; i++)
{
    scanf ("%d %d", &a[i], &b[i]);
    p[a[i]] = b[i], p[b[i]] = a[i];
    pos[a[i]] = pos[b[i]] = i;
}
build (1, 1, 2 * N);
int ans = 1;
for (int i=1; i<=N; i++)
    if (ap[i] == 0)
        dfs (i, +1), ans = (ans + ans) % mod;
vector < int > v[2];
for (int i=1; i<=N; i++)
    v[ap[i] - 1].push_back (i);
check (v[0]), check (v[1]);
printf ("%d\n", ans);
return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:112:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d", &N);
 ~~~~~~^~~~~~~~~~
port_facility.cpp:115:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d", &a[i], &b[i]);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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