Submission #85542

#	Time	Username	Problem	Language	Result	Execution time	Memory
85542		zoooma13	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	610 ms	126456 KiB

long_mansion

#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)){
                en[i] = max(en[i] ,en[st[i]-1]);
                st[i] = st[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 (stderr)

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: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 75 / 75