Submission #83514

#	Time	Username	Problem	Language	Result	Execution time	Memory
83514		nikolapesic2802	Long Mansion (JOI17_long_mansion)	C++14	0 / 100	3083 ms	9716 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()

struct minSegmentTree{
    int n;
    vector<int> minn;
    void init(int nn)
    {
        n=nn;
        minn.resize(2*n);
        for(int i=0;i<2*n;i++)
        {
            minn[i]=INT_MAX;
        }
    }
    void set(int i,int k)
    {
        i+=n;
        minn[i]=k;
        i>>=1;
        for(;i;i>>=1)
        {
            //printf("%i %i %i\n",i,minn[2*i],minn[2*i+1]);
            minn[i]=min(minn[2*i],minn[2*i+1]);
        }
    }
    int get(int l,int r)
    {
        int m=INT_MAX;
        for(l+=n,r+=n;l<=r;l>>=1,r>>=1)
        {
            if(l%2==1)
            {
                m=min(m,minn[l]);
                l++;
            }
            if(r%2==0)
            {
                m=min(m,minn[r]);
                r--;
            }
        }
        return m;
    }
};
struct maxSegmentTree{
    int n;
    vector<int> minn;
    void init(int nn)
    {
        n=nn;
        minn.resize(2*n);
        for(int i=0;i<2*n;i++)
        {
            minn[i]=-1;
        }
    }
    void set(int i,int k)
    {
        i+=n;
        minn[i]=k;
        i>>=1;
        for(;i;i>>=1)
        {
            minn[i]=max(minn[2*i],minn[2*i+1]);
            //printf("maxx od %i: %i\n",i,minn[i]);
        }
    }
    int get(int l,int r)
    {
        int m=-1;
        for(l+=n,r+=n;l<=r;l>>=1,r>>=1)
        {
            if(l%2==1)
            {
                //printf("uzimam %i\n",l);
                m=max(m,minn[l]);
                l++;
            }
            if(r%2==0)
            {
                //printf("uzimam %i\n",r);
                m=max(m,minn[r]);
                r--;
            }
        }
        return m;
    }
};
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);
    maxSegmentTree maxx;
    maxx.init(n-1);
    minSegmentTree minn;
    minn.init(n-1);
    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;
        //printf("Postavljam %i na %i\n",i,keys[cor[i]]);
        minn.set(i,keys[cor[i]]);
    }
    fill(keys.begin(),keys.end(),INT_MAX);
    for(int i=n-1;i>0;i--)
    {
        for(auto p:sobe[i])
            keys[p]=i;
        //printf("postavljam %i na %i\n",i-1,keys[cor[i-1]]);
        maxx.set(i-1,keys[cor[i-1]]);
    }
    int first=0;
    fill(keys.begin(),keys.end(),-1);
    for(int i=0;i<n-1;i++)
    {
        for(auto p:sobe[i])
            keys[p]=i;
        if(keys[cor[i]]==-1)
        {
            first=i;
            break;
        }
    }
    vector<int> levo(n),desno(n);
    levo[0]=0;
    desno[0]=first;
    //printf("%i %i\n",levo[0],desno[0]);
    for(int i=1;i<n;i++)
    {
        int last=maxx.get(i-1,i-1);
        int m;
        if(last==INT_MAX)
        {
            m=-1;
        }
        else
        {
            if(i<=last-1)
                m=minn.get(i,last-1);
            else
                m=i;
        }
        //printf("%i %i\n",last,m);
        if(m==i&&desno[i-1]>0)
        {
            desno[i]=desno[i-1];
            levo[i]=levo[i-1]+1;
        }
        if(m!=i)
        {
            int l=i-1,r=n-1;
            while(l<r)
            {
                int midd=(l+r)/2;
                if(midd==i-1)
                {
                    break;
                }
                int m=minn.get(i,midd);
                if(m==i)
                {
                    l=midd;
                    if(l==n-2&&r==n-1)
                    {
                        l=r;
                    }
                }
                else
                {
                    r=midd-1;
                }
            }
            desno[i]=l-i+1;
            levo[i]=0;
        }
        if(m==i&&desno[i-1]==0)
        {
            int l=i-1,r=n-1;
            while(l<r)
            {
                int midd=(l+r)/2;
                //printf("%i %i %i  %i\n",l,r,midd,i);
                if(midd==i-1)
                {
                    break;
                }
                int m=minn.get(i,midd);
                if(m>=i-levo[i-1]-1)
                {
                    l=midd;
                    if(l==n-2&&r==n-1)
                    {
                        l=r;
                    }
                    //printf("%i\n",l);
                }
                else
                {
                    r=midd-1;
                }
            }
            desno[i]=l-i+1;
            levo[i]=levo[i-1]+1;
        }
        //printf("%i %i\n",levo[i],desno[i]);
    }
    int q;
    scanf("%i",&q);
    for(int i=0;i<q;i++)
    {
        int x,y;
        scanf("%i %i",&x,&y);
        x--;
        y--;
        if(x>=y)
        {
            if(levo[x]>=x-y)
            {
                printf("YES\n");
            }
            else
            {
                printf("NO\n");
            }
        }
        else
        {
            if(desno[x]>=y-x)
            {
                printf("YES\n");
            }
            else
            {
                printf("NO\n");
            }
        }
    }
    return 0;
}

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:102:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
long_mansion.cpp:105: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:114:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&b);
         ~~~~~^~~~~~~~~
long_mansion.cpp:118:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%i",&a);
             ~~~~~^~~~~~~~~
long_mansion.cpp:234:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&q);
     ~~~~~^~~~~~~~~
long_mansion.cpp:238: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: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 15
• Subtask 4: 0 / 75