Submission #21040

#	Time	Username	Problem	Language	Result	Execution time	Memory
21040		ainta	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	1363 ms	65844 KiB

long_mansion

#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#define SZ 524288
using namespace std;
vector<int>E[501000];
int C[501000], L[501000], R[501000], LL[501000], RR[501000];
int n, Q;
set<int>Set;
struct point{
    int x, num;
    bool operator<(const point &p)const{
        return x<p.x;
    }
}ord[501000];
struct Tree{
    int Mn, Mx;
}IT[SZ+SZ];
Tree Get(int b, int e){
    b += SZ, e += SZ;
    Tree r = {n+1,0};
    while(b<=e){
        r.Mn = min(r.Mn,min(IT[b].Mn,IT[e].Mn));
        r.Mx = max(r.Mx,max(IT[b].Mx,IT[e].Mx));
        b=(b+1)>>1,e=(e-1)>>1;
    }
    return r;
}
int main(){
    int i, a, b;
    scanf("%d",&n);
    for(i=1;i<n;i++)scanf("%d",&C[i]);
    for(i=1;i<=n;i++){
        scanf("%d",&a);
        while(a--){
            scanf("%d",&b);
            E[b].push_back(i);
        }
    }
    for(i=1;i<=n;i++){
        a = C[i-1];
        if(E[a].empty()) L[i] = n+1;
        else{
            int t = lower_bound(E[a].begin(),E[a].end(),i)-E[a].begin();
            if(t == E[a].size())L[i] = n+1;
            else L[i] = E[a][t];
        }
    }
    for(i=n;i>=1;i--){
        a = C[i];
        if(E[a].empty()) R[i] = 0;
        else{
            int t = lower_bound(E[a].begin(),E[a].end(),i+1)-E[a].begin();
            if(t == 0)R[i] = 0;
            else R[i] = E[a][t-1];
        }
    }
    for(i=1;i<=n;i++){
        ord[i].x=L[i],ord[i].num = i;
        Set.insert(i);
    }
    sort(ord+1,ord+n+1);
    int pv = 1;
    for(i=1;i<=n;i++){
        LL[i] = n+1;
        while(pv<=n && ord[pv].x <= i){
            Set.erase(ord[pv].num);
            pv++;
        }
        if(Set.empty())continue;
        auto it = Set.lower_bound(R[i]+1);
        if(it!=Set.end() && (*it) <= i){
            LL[i] = *it;
        }
    }
    Set.clear();
    for(i=1;i<=n;i++){
        ord[i].x=R[i],ord[i].num = i;
        Set.insert(i);
    }
    sort(ord+1,ord+n+1);
    pv = n;
    for(i=n;i>=1;i--){
        RR[i] = 0;
        while(pv>=1 && ord[pv].x >= i){
            Set.erase(ord[pv].num);
            pv--;
        }
        if(Set.empty())continue;
        auto it = Set.lower_bound(L[i]);
        if(it!=Set.begin()){
            it--;
            if((*it) >= i)RR[i] = *it;
        }
    }
    scanf("%d",&Q);
    for(i=1;i<=n;i++){
        a = SZ+i;
        IT[a].Mn = LL[i], IT[a].Mx = RR[i];
        while(a!=1){
            a>>=1;
            IT[a].Mn = min(IT[a+a].Mn,IT[a+a+1].Mn);
            IT[a].Mx = max(IT[a+a].Mx,IT[a+a+1].Mx);
        }
    }
    while(Q--){
        scanf("%d%d",&a,&b);
        if(a<b){
            if(Get(a,b-1).Mn <= a)puts("NO");
            else puts("YES");
        }
        else{
            if(Get(b+1,a).Mx >= a)puts("NO");
            else puts("YES");
        }
    }
}

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:46:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(t == E[a].size())L[i] = n+1;
                  ^
long_mansion.cpp:32:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
long_mansion.cpp:33:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<n;i++)scanf("%d",&C[i]);
                                      ^
long_mansion.cpp:35:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a);
                       ^
long_mansion.cpp:37:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&b);
                           ^
long_mansion.cpp:97:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&Q);
                   ^
long_mansion.cpp:108:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
                            ^

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