oj.uz

Submission #85540

# Submission time Handle Problem Language Result Execution time Memory
85540 2018-11-20T20:05:34 Z zoooma13 Long Mansion (JOI17_long_mansion) C++14
0 / 100
 508 ms 28900 KB 
#include <bits/stdc++.h>
using namespace std;

#define MAX_N 500005

int N;
int C[MAX_N];
int B ,K;
vector <int> Keys[MAX_N];
int Q;
int X ,Y;

int last[MAX_N];
int nl[MAX_N] ,nr[MAX_N];
int st[MAX_N] ,en[MAX_N];

int main()
{
    scanf("%d",&N);
    for(int i=0; i<N-1; i++)
        scanf("%d",&C[i]);
    for(int i=0; i<N; i++)
    {
        scanf("%d",&B);
        while(B--){
            scanf("%d",&K);
            Keys[i].push_back(K);
        }
    }

    memset(last ,-1 ,sizeof last);
    for(int i=0; i<N-1; i++){
        for(int j : Keys[i])
            last[j] = i;
        nl[i] = last[C[i]];
    }
    memset(last ,-1 ,sizeof last);
    for(int i=N-2; ~i; i--){
        for(int j : Keys[i+1])
            last[j] = i+1;
        nr[i] = last[C[i]];
    }

    auto can_left = [&](int i){
        return (st[i] > 0 && ~nr[st[i]-1] && nr[st[i]-1] <= en[i]);
    };
    auto can_right = [&](int i){
        return (en[i] < N-1 && ~nl[en[i]] && st[i] <= nl[en[i]]);
    };

    for(int i=0; i<N; i++)
    {
        st[i] = en[i] = i;
        while(true)
        {
            if(can_left(i)){
                st[i] = st[st[i]-1];
                en[i] = max(en[i] ,en[st[i]-1]);
            }
            else if(can_right(i))
                en[i]++;
            else
                break;
        }
    }

    scanf("%d",&Q);
    while(Q--)
    {
        scanf("%d%d",&X,&Y); X-- ,Y--;
        printf(st[X]<=Y&&Y<=en[X] ? "YES\n" : "NO\n");
    }
}

Compilation message

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&N);
     ~~~~~^~~~~~~~~
long_mansion.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&C[i]);
         ~~~~~^~~~~~~~~~~~
long_mansion.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&B);
         ~~~~~^~~~~~~~~
long_mansion.cpp:26:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&K);
             ~~~~~^~~~~~~~~
long_mansion.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&Q);
     ~~~~~^~~~~~~~~
long_mansion.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&X,&Y); X-- ,Y--;
         ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 75.0

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