Submission #235231

#TimeUsernameProblemLanguageResultExecution timeMemory
235231MvCLong Mansion (JOI17_long_mansion)C++14
0 / 100
955 ms28980 KiB
#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> #define rc(x) return cout<<x<<endl,0 #define pb push_back #define mkp make_pair #define in insert #define er erase #define fd find #define fr first #define sc second #define all(x) x.begin(),x.end() typedef long long ll; typedef long double ld; const ll INF=0x3f3f3f3f3f3f3f3f; const ll llinf=(1LL<<62); const int inf=(1<<30); const int nmax=5e5+50; const ll mod=1e9+7; using namespace std; int n,i,l,r,mid,lf[nmax],rg[nmax],f[nmax],g[nmax],smn[4*nmax],smx[4*nmax],c[nmax],x,y,rsl[nmax],rsr[nmax],q; vector<int>a[nmax]; void bldmx(int nod,int l,int r,int *ar) { if(l==r) { smx[nod]=ar[l]; return; } int mid=(l+r)/2; bldmx(2*nod,l,mid,ar); bldmx(2*nod+1,mid+1,r,ar); smx[nod]=max(smx[2*nod],smx[2*nod+1]); } int qmx(int nod,int l,int r,int tl,int tr) { if(tr<l || tl>r)return -1; if(tl<=l && r<=tr)return smx[nod]; int mid=(l+r)/2; return max(qmx(2*nod,l,mid,tl,tr),qmx(2*nod+1,mid+1,r,tl,tr)); } void bldmn(int nod,int l,int r,int *ar) { if(l==r) { smn[nod]=ar[l]; return; } int mid=(l+r)/2; bldmn(2*nod,l,mid,ar); bldmn(2*nod+1,mid+1,r,ar); smn[nod]=min(smn[2*nod],smn[2*nod+1]); } int qmn(int nod,int l,int r,int tl,int tr) { if(tr<l || tl>r)return inf; if(tl<=l && r<=tr)return smn[nod]; int mid=(l+r)/2; return min(qmn(2*nod,l,mid,tl,tr),qmn(2*nod+1,mid+1,r,tl,tr)); } int main() { //freopen("sol.in","r",stdin); //freopen("sol.out","w",stdout); //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0); cin>>n; for(i=1;i<n;i++)cin>>c[i]; for(i=1;i<=n;i++) { cin>>y; while(y--) { cin>>x; a[x].pb(i); } } for(i=1;i<=n;i++) { lf[i]=-1,rg[i]=inf; if(i>1 && !a[c[i-1]].empty() && a[c[i-1]][0]<i)lf[i]=*(--lower_bound(all(a[c[i-1]]),i)); if(i<n && !a[c[i]].empty() && a[c[i]].back()>i)rg[i]=*(upper_bound(all(a[c[i]]),i)); //cout<<lf[i]<<" "<<rg[i]<<endl; } bldmx(1,1,n,rg); bldmn(1,1,n,lf); for(i=1;i<=n;i++) { f[i]=-1,g[i]=inf; if(lf[i]!=-1) { l=lf[i],r=i-2; while(l<=r) { mid=(l+r)/2; if(qmx(1,1,n,lf[i],mid)>=i)r=mid-1; else l=mid+1; } f[i]=r; if(rg[lf[i]]>=i)f[i]=-1; } if(rg[i]!=inf) { l=i+2,r=rg[i]; while(l<=r) { mid=(l+r)/2; if(qmn(1,1,n,mid,rg[i])<=i)l=mid+1; else r=mid-1; } g[i]=l; if(lf[rg[i]]<=i)g[i]=inf; } cout<<f[i]<<" "<<g[i]<<endl; } bldmx(1,1,n,g); bldmn(1,1,n,f); for(i=1;i<=n;i++) { l=i,r=n,rsr[i]=i; while(l<=r) { mid=(l+r)/2; if(qmn(1,1,n,i,mid)<i-1)r=mid-1; else l=mid+1; } rsr[i]=r; l=1,r=i,rsl[i]=i; while(l<=r) { mid=(l+r)/2; if(qmx(1,1,n,mid,i)>i+1)l=mid+1; else r=mid-1; } rsl[i]=l; //cout<<rsl[i]<<" "<<rsr[i]<<endl; } cin>>q; while(q--) { cin>>x>>y; if((x<y && y<=rsr[x]) || (x>y && y>=rsl[x]))cout<<"YES\n"; else cout<<"NO\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...