제출 #47102

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
47102		SpaimaCarpatilor	Long Mansion (JOI17_long_mansion)	C++17	0 / 100	3 ms	804 KiB

long_mansion

#include<bits/stdc++.h>

using namespace std;

const int NMAX = 1000;//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];
    }
}

void processQueries ()
{
    int Q;
    scanf ("%d", &Q);
    while (Q --)
    {
        int x, y;
        scanf ("%d %d", &x, &y);
        bool ans = 1;
        if (x < y)
        {
            for (int i=x; i<y; i++)
                if (minL[i] <= x)
                    ans = 0;
        }
        else
        {
            for (int i=y + 1; i<=x; i++)
                if (maxR[i] >= 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 ();
processQueries ();

return 0;
}

컴파일 시 표준 에러 (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:105:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d", &Q);
     ~~~~~~^~~~~~~~~~
long_mansion.cpp:109: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: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 15
• Subtask 4: 0 / 75