Submission #83925

#	Time	Username	Problem	Language	Result	Execution time	Memory
83925		Bodo171	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	1330 ms	137316 KiB

long_mansion

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=500005;
struct intv
{
    int l,r;
}in[nmax];
vector<int> v[nmax];
int rmq[20][nmax];
int st[nmax],c[nmax],lst[nmax],nxt[nmax];
int n,q,i,j,p,nr,x,u,y;
bool ok;
void mrg(intv &a,intv b)
{
    if(b.l<a.l) a.l=b.l;
    if(b.r>a.r) a.r=b.r;
}
void dublaje()
{
    for(i=1;i<=18;i++)
        for(j=1;j<=n-(1<<i)+1;j++)
           rmq[i][j]=min(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]);
}
int extinde(int l,int r)
{
    int t=r+1;
    for(p=18;p>=0;p--)
        if(t+(1<<p)-1<=n&&rmq[p][t]>=l)
               t+=(1<<p);
    return (t-1);
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n;
    for(i=1;i<n;i++)
        cin>>c[i];
    for(i=1;i<=n;i++)
    {
        cin>>nr;
        for(j=1;j<=nr;j++)
        {
            cin>>x;
            v[i].push_back(x);
        }
    }
    for(i=1;i<n;i++)
    {
        for(j=0;j<v[i].size();j++)
            lst[v[i][j]]=i;
        rmq[0][i+1]=lst[c[i]];
    }
    dublaje();
    for(i=1;i<=n;i++)
        lst[i]=n+1;
    for(i=n;i>=1;i--)
    {
        nxt[i]=lst[c[i]];
        for(j=0;j<v[i].size();j++)
            lst[v[i][j]]=i;

    }
    for(i=1;i<=n;i++)
    {
        in[i].l=i;in[i].r=i;
        ok=1;
        in[i].r=extinde(in[i].l,in[i].r);
        while(u>0&&ok)
        {
            ok=0;
            if(nxt[st[u]]<=in[i].r)
            {
                ok=1;
                mrg(in[i],in[st[u]]);
                u--;
            }
            in[i].r=extinde(in[i].l,in[i].r);
        }
        st[++u]=i;
    }
    cin>>q;
    for(i=1;i<=q;i++)
    {
        cin>>x>>y;
        if(y>=in[x].l&&y<=in[x].r) cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:52:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<v[i].size();j++)
                 ~^~~~~~~~~~~~
long_mansion.cpp:62:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<v[i].size();j++)
                 ~^~~~~~~~~~~~

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