Submission #47104

#	Time	Username	Problem	Language	Result	Execution time	Memory
47104		SpaimaCarpatilor	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	742 ms	262144 KiB

long_mansion

#include<bits/stdc++.h>

using namespace std;

const int NMAX = 500009;
int N, last[NMAX], lft[NMAX], rgt[NMAX], C[NMAX], minL[NMAX], maxR[NMAX];
vector < int > v[NMAX];

void read ()
{
    scanf ("%d", &N);
    for (int i=1; i<N; i++)
        scanf ("%d", &C[i]);
    for (int i=1; i<=N; i++)
    {
        int l, x;
        scanf ("%d", &l);
        while (l --)
            scanf ("%d", &x),
            v[i].push_back (x),
            last[x] = i;
        if (i < N)
            lft[i] = last[C[i]];
    }
    for (int i=1; i<=N; i++)
        last[i] = 0;
    for (int i=N; i>=2; i--)
    {
        for (auto it : v[i])
            last[it] = i;
        if (last[C[i - 1]] == 0) rgt[i - 1] = N + 1;
        else rgt[i - 1] = last[C[i - 1]];
    }
}

namespace segtree {
    int ma[4 * NMAX], aintVal[NMAX];

    void build (int nod, int st, int dr)
    {
        if (st == dr)
        {
            ma[nod] = aintVal[st];
            return ;
        }
        int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
        build (f1, st, mij);
        build (f2, mij + 1, dr);
        ma[nod] = max (ma[f1], ma[f2]);
    }

    int firstBigger (int nod, int st, int dr, int x, int y, int minVal)
    {
        if (x > y) return -1;
        int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
        if (x <= st && dr <= y)
        {
            if (ma[nod] <= minVal) return -1;
            if (st == dr) return st;
            if (ma[f1] > minVal) return firstBigger (f1, st, mij, x, y, minVal);
            return firstBigger (f2, mij + 1, dr, x, y, minVal);
        }
        if (x <= mij)
        {
            int curr = firstBigger (f1, st, mij, x, y, minVal);
            if (curr != -1) return curr;
        }
        if (mij < y)
            return firstBigger (f2, mij + 1, dr, x, y, minVal);
        return -1;
    }
};

void buildMinL ()
{
    for (int i=1; i<=N; i++)
        segtree::aintVal[i] = (i == 1 ? N + 1 : rgt[i - 1]);
    segtree::build (1, 1, N);
    for (int i=1; i<=N; i++)
    {
        minL[i] = segtree::firstBigger (1, 1, N, lft[i] + 1, i, i);
        if (minL[i] == -1)
            minL[i] = N + 1;
    }
}

void buildMaxR ()
{
    for (int i=1; i<=N; i++)
        segtree::aintVal[i] = -(i == N ? 0 : lft[i]);
    reverse (segtree::aintVal + 1, segtree::aintVal + N + 1);
    segtree::build (1, 1, N);
    for (int i=1; i<=N; i++)
    {
        int lEnd = i, rEnd = rgt[i - 1] - 1;
        maxR[i] = segtree::firstBigger (1, 1, N, N + 1 - rEnd, N + 1 - lEnd, -i);
        if (maxR[i] == -1) maxR[i] = 0;
        else maxR[i] = N + 1 - maxR[i];
    }
}

namespace RMQ {
    int mi[19][NMAX], ma[19][NMAX], lg[NMAX];
    void buildRmq ()
    {
        for (int i=1; i<=N; i++)
        {
            lg[i] = lg[i - 1];
            if ((2 << lg[i]) <= i) lg[i] ++;
        }
        for (int i=1; i<=N; i++)
            mi[0][i] = minL[i],
            ma[0][i] = maxR[i];
        for (int i=1; i<=lg[N]; i++)
            for (int j=1; j + (1 << i) - 1 <= N; j++)
                mi[i][j] = min (mi[i - 1][j], mi[i - 1][j + (1 << (i - 1))]),
                ma[i][j] = max (ma[i - 1][j], ma[i - 1][j + (1 << (i - 1))]);
    }

    int getMin (int l, int r)
    {
        int p = lg[r - l + 1];
        return min (mi[p][l], mi[p][r - (1 << p) + 1]);
    }

    int getMax (int l, int r)
    {
        int p = lg[r - l + 1];
        return max (ma[p][l], ma[p][r - (1 << p) + 1]);
    }
};

void processQueries ()
{
    int Q;
    scanf ("%d", &Q);
    while (Q --)
    {
        int x, y;
        scanf ("%d %d", &x, &y);
        bool ans = 1;
        if (x < y && RMQ::getMin (x, y - 1) <= x) ans = 0;
        else
        if (y < x && RMQ::getMax (y + 1, x) >= x) ans = 0;
        if (ans) printf ("YES\n");
        else printf ("NO\n");
    }
}

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

read ();
buildMinL ();
buildMaxR ();
RMQ::buildRmq ();
processQueries ();

return 0;
}

Compilation message (stderr)

long_mansion.cpp: In function 'void read()':
long_mansion.cpp:11:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d", &N);
     ~~~~~~^~~~~~~~~~
long_mansion.cpp:13:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d", &C[i]);
         ~~~~~~^~~~~~~~~~~~~
long_mansion.cpp:17:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d", &l);
         ~~~~~~^~~~~~~~~~
long_mansion.cpp:20:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf ("%d", &x),
             ~~~~~~~~~~~~~~~~~~ 
             v[i].push_back (x),
             ~~~~~~~~~~~~~~~~~~^~
             last[x] = i;
             ~~~~~~~~~~~        
long_mansion.cpp: In function 'void processQueries()':
long_mansion.cpp:136:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d", &Q);
     ~~~~~~^~~~~~~~~~
long_mansion.cpp:140:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d %d", &x, &y);
         ~~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 75 / 75