Submission #363532

#	Time	Username	Problem	Language	Result	Execution time	Memory
363532		denkendoemeer	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	439 ms	52460 KiB

long_mansion

#include<bits/stdc++.h>
using namespace std;
int c[500005],last[500005],pre[500005],nex[500005],st[500005],dr[500005];
vector<int>a[500005];
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int n,i;
    scanf("%d",&n);
    for(i=1;i<n;i++)
        scanf("%d",&c[i]);
    for(i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        a[i].resize(x);
        int j;
        for(j=0;j<x;j++)
            scanf("%d",&a[i][j]);
    }
    for(i=1;i<n;i++){
        for(auto it:a[i])
            last[it]=i;
        pre[i]=last[c[i]];
    }
    for(i=1;i<=n;i++)
        last[i]=n+1;
    for(i=n;i>=2;i--){
        for(auto it:a[i])
            last[it]=i;
        nex[i-1]=last[c[i-1]];
    }
    for(i=1;i<=n;i++){
        int l=i,r=i;
        while(1){
            if (l>1 && nex[l-1]<=r){
                r=max(r,dr[l-1]);
                l=st[l-1];
                continue;
            }
            if (r+1<=n && pre[r]>=l){
                r++;
                continue;
            }
            break;
        }
        st[i]=l;
        dr[i]=r;
    }
    int q,x,y;
    scanf("%d",&q);
    for(i=1;i<=q;i++){
        scanf("%d%d",&x,&y);
        if (st[x]<=y && y<=dr[x])
            printf("YES\n");
        else
            printf("NO\n");
    }
return 0;
}

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   10 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
long_mansion.cpp:12:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   12 |         scanf("%d",&c[i]);
      |         ~~~~~^~~~~~~~~~~~
long_mansion.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   15 |         scanf("%d",&x);
      |         ~~~~~^~~~~~~~~
long_mansion.cpp:19:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   19 |             scanf("%d",&a[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~
long_mansion.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
long_mansion.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~

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