Submission #83516

#	Time	Username	Problem	Language	Result	Execution time	Memory
83516		nikolapesic2802	Long Mansion (JOI17_long_mansion)	C++14	25 / 100	441 ms	263168 KiB

long_mansion

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll long long
#define pb push_back

using namespace std;
using namespace __gnu_pbds;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; ///find_by_order(),order_of_key()
const int N=5*1e5+5;
vector<int> hi(N),lo(N),l(N),r(N);
bool on(int l,int r,int x){return x>=l&&x<=r;}
bool can(int l,int r,int x){return on(l,r,hi[x])||on(l,r,lo[x]);}
int main()
{
    int n;
    scanf("%i",&n);
    vector<int> cor(n-1);
    for(int i=0;i<n-1;i++)
        scanf("%i",&cor[i]);
    vector<vector<int> > sobe(n);
    for(int i=0;i<n;i++)
    {
        int b;
        scanf("%i",&b);
        for(int j=0;j<b;j++)
        {
            int a;
            scanf("%i",&a);
            sobe[i].pb(a);
        }
    }
    vector<int> keys(n,-1);
    for(int i=0;i<n-1;i++)
    {
        for(auto p:sobe[i])
            keys[p]=i;
        lo[i]=keys[cor[i]];
    }
    fill(keys.begin(),keys.end(),-1);
    for(int i=n-1;i>0;i--)
    {
        for(auto p:sobe[i])
            keys[p]=i;
        hi[i-1]=keys[cor[i-1]];
    }
    for(int i=0;i<n;i++)
    {
        l[i]=r[i]=i;
        while(true)
        {
            if(l[i]>0&&can(l[i],r[i],l[i]-1))
            {
                r[i]=max(r[i],r[l[i]-1]);
                l[i]=l[l[i]-1];
            }
            else
                if(r[i]<n-1&&can(l[i],r[i],r[i]))
                    r[i]++;
                else
                    break;
        }
    }
    int q;
    scanf("%i",&q);
    for(int i=0;i<q;i++)
    {
        int x,y;
        scanf("%i %i",&x,&y);
        x--;
        y--;
        if(on(l[x],r[x],y))
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

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("%i",&n);
     ~~~~~^~~~~~~~~
long_mansion.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&cor[i]);
         ~~~~~^~~~~~~~~~~~~~
long_mansion.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&b);
         ~~~~~^~~~~~~~~
long_mansion.cpp:31:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%i",&a);
             ~~~~~^~~~~~~~~
long_mansion.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&q);
     ~~~~~^~~~~~~~~
long_mansion.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i %i",&x,&y);
         ~~~~~^~~~~~~~~~~~~~~

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