Submission #958580

#	Time	Username	Problem	Language	Result	Execution time	Memory
958580		Alish	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	294 ms	59888 KiB

long_mansion

#include <bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp              make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl;
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("tests.in" , "r" , stdin) ;

ll mod = 1e9+7 ;

const int N = 5e5+23;

int seg[4*N];
int L[N], R[N];
vector<int> a[N];
int b[N], c[N];
int ind[N], pre[N], nxt[N];
int n, q;

void build(int l=0, int r=n+2, int ind=0){
    if(r-l==1){
        seg[ind]=pre[l];
        return;
    }
    int mid=(r+l)>>1;
    build(l, mid, 2*ind+1); build(mid, r, 2*ind+2);
    seg[ind]=min(seg[2*ind+1], seg[2*ind+2]);
}

int get(int lx, int rx, int x, int l=0, int r=n+2, int ind=0){
    if(lx>=r || rx<=l || seg[ind]>=x) return -1;
    if(r-l==1) return l;
    int mid=(r+l)>>1;
    int r1=get(lx, rx, x, l, mid, 2*ind+1);
    if(r1==-1) return get(lx, rx, x, mid, r, 2*ind+2);
    return r1;
}

int main()
{
    fast_io
    cin>>n;
    for (int i=1; i<n; i++) cin>>c[i];
    for (int i=1; i<=n; i++){
        cin>>b[i];
        for (int j=0; j<b[i]; j++){
            int x; cin>>x;
            a[i].pb(x);
        }
    }
    for (int i=1; i<=n; i++){
        pre[i]=ind[c[i-1]];
        for (int j: a[i]) ind[j]=i;
    }
    for (int i=0; i<=n; i++) ind[i]=n+1;
    for (int i=n; i>=1; i--){
        nxt[i]=ind[c[i]];
        for (int j: a[i]) ind[j]=i;
    }
    nxt[0]=n+1;
    pre[n+1]=0;
    build();
    for (int i=1; i<=n; i++){
        L[i]=R[i]=i;
        while(1){
            int preL=L[i], preR=R[i];
            R[i]=get(R[i]+1, n+2, L[i])-1;
            if(nxt[L[i]-1]<=R[i]) L[i]=L[L[i]-1];
            if(L[i]==preL && R[i]==preR) break;
        }
    }
    cin>>q;
    while(q--){
        int x, y; cin>>x>>y;
        if(L[x]<=y && y<=R[x]) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }

}

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