oj.uz

Submission #47103

# Submission time Handle Problem Language Result Execution time Memory
47103 2018-04-27T15:28:16 Z SpaimaCarpatilor Long Mansion (JOI17_long_mansion) C++17
10 / 100
 782 ms 84432 KB 
#include<bits/stdc++.h>

using namespace std;

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

Compilation message

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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 760 KB Output is correct
2 Correct 13 ms 1012 KB Output is correct
3 Correct 12 ms 1180 KB Output is correct
4 Correct 8 ms 1180 KB Output is correct
5 Correct 8 ms 1296 KB Output is correct
6 Correct 8 ms 1408 KB Output is correct
7 Correct 9 ms 1408 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 760 KB Output is correct
2 Correct 13 ms 1012 KB Output is correct
3 Correct 12 ms 1180 KB Output is correct
4 Correct 8 ms 1180 KB Output is correct
5 Correct 8 ms 1296 KB Output is correct
6 Correct 8 ms 1408 KB Output is correct
7 Correct 9 ms 1408 KB Output is correct
8 Correct 427 ms 7456 KB Output is correct
9 Correct 446 ms 11812 KB Output is correct
10 Correct 513 ms 16484 KB Output is correct
11 Correct 782 ms 21536 KB Output is correct
12 Correct 335 ms 24860 KB Output is correct
13 Correct 166 ms 29568 KB Output is correct
14 Correct 163 ms 33752 KB Output is correct
15 Correct 250 ms 38140 KB Output is correct
16 Correct 479 ms 42256 KB Output is correct
17 Correct 169 ms 46368 KB Output is correct
18 Correct 169 ms 50728 KB Output is correct
19 Correct 186 ms 55072 KB Output is correct
20 Correct 542 ms 59492 KB Output is correct
21 Correct 493 ms 63512 KB Output is correct
22 Correct 295 ms 67404 KB Output is correct
23 Correct 223 ms 71628 KB Output is correct
24 Correct 246 ms 75940 KB Output is correct
25 Correct 265 ms 80084 KB Output is correct
26 Correct 188 ms 84432 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 84432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 760 KB Output is correct
2 Correct 13 ms 1012 KB Output is correct
3 Correct 12 ms 1180 KB Output is correct
4 Correct 8 ms 1180 KB Output is correct
5 Correct 8 ms 1296 KB Output is correct
6 Correct 8 ms 1408 KB Output is correct
7 Correct 9 ms 1408 KB Output is correct
8 Correct 427 ms 7456 KB Output is correct
9 Correct 446 ms 11812 KB Output is correct
10 Correct 513 ms 16484 KB Output is correct
11 Correct 782 ms 21536 KB Output is correct
12 Correct 335 ms 24860 KB Output is correct
13 Correct 166 ms 29568 KB Output is correct
14 Correct 163 ms 33752 KB Output is correct
15 Correct 250 ms 38140 KB Output is correct
16 Correct 479 ms 42256 KB Output is correct
17 Correct 169 ms 46368 KB Output is correct
18 Correct 169 ms 50728 KB Output is correct
19 Correct 186 ms 55072 KB Output is correct
20 Correct 542 ms 59492 KB Output is correct
21 Correct 493 ms 63512 KB Output is correct
22 Correct 295 ms 67404 KB Output is correct
23 Correct 223 ms 71628 KB Output is correct
24 Correct 246 ms 75940 KB Output is correct
25 Correct 265 ms 80084 KB Output is correct
26 Correct 188 ms 84432 KB Output is correct
27 Incorrect 22 ms 84432 KB Output isn't correct
28 Halted 0 ms 0 KB -