Submission #282445

#	Time	Username	Problem	Language	Result	Execution time	Memory
282445		MKopchev	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	446 ms	43192 KiB

long_mansion

#include<bits/stdc++.h>
using namespace std;

const int nmax=5e5+42;

int n,inp[nmax];

vector<int> seen[nmax];

int can_l[nmax],can_r[nmax];

bool test(int val,int l,int r)
{
    if(seen[val].size()==0)return 0;

    int p=lower_bound(seen[val].begin(),seen[val].end(),l)-seen[val].begin();

    if(p<seen[val].size()&&seen[val][p]<=r)return 1;

    return 0;
}
int main()
{
    scanf("%i",&n);

    for(int i=1;i<n;i++)scanf("%i",&inp[i]);

    for(int i=1;i<=n;i++)
    {
        int sz,val;
        scanf("%i",&sz);

        for(int j=1;j<=sz;j++)
        {
            scanf("%i",&val);
            seen[val].push_back(i);
        }
    }

    for(int i=1;i<=n;i++)
    {
        can_l[i]=i;
        can_r[i]=i;

        while(can_l[i]!=1||can_r[i]!=n)
        {
            if(can_l[i]!=1&&test(inp[can_l[i]-1],can_l[i],can_r[i]))
            {
                can_l[i]--;

                can_r[i]=max(can_r[i],can_r[can_l[i]]);

                can_l[i]=min(can_l[i],can_l[can_l[i]]);
            }
            else if(can_r[i]!=n&&test(inp[can_r[i]],can_l[i],can_r[i]))can_r[i]++;
            else break;
        }
    }

    int q;
    scanf("%i",&q);

    for(int i=1;i<=q;i++)
    {
        int le,ri;
        scanf("%i%i",&le,&ri);

        if(can_l[le]<=ri&&ri<=can_r[le])printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

Compilation message (stderr)

long_mansion.cpp: In function 'bool test(int, int, int)':
long_mansion.cpp:18:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     if(p<seen[val].size()&&seen[val][p]<=r)return 1;
      |        ~^~~~~~~~~~~~~~~~~
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |     scanf("%i",&n);
      |     ~~~~~^~~~~~~~~
long_mansion.cpp:26:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   26 |     for(int i=1;i<n;i++)scanf("%i",&inp[i]);
      |                         ~~~~~^~~~~~~~~~~~~~
long_mansion.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |         scanf("%i",&sz);
      |         ~~~~~^~~~~~~~~~
long_mansion.cpp:35:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |             scanf("%i",&val);
      |             ~~~~~^~~~~~~~~~~
long_mansion.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |     scanf("%i",&q);
      |     ~~~~~^~~~~~~~~
long_mansion.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |         scanf("%i%i",&le,&ri);
      |         ~~~~~^~~~~~~~~~~~~~~~

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