Submission #260696

#TimeUsernameProblemLanguageResultExecution timeMemory
260696fadi57Long Mansion (JOI17_long_mansion)C++14
10 / 100
3061 ms27508 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int mx=500020; int c[mx]; ll b[mx]; vector<ll>keys[mx]; ll mxright[mx]; ll mxleft[mx]; ll n,m; int leftt[mx];int rightt[mx]; int last[mx]; int canr(int i){ if(leftt[mxright[i]]>=mxleft[i]&&leftt[mxright[i]]!=-1&&mxright[i]<n){ return 1; }return 0; }int canl(int i){ if(rightt[mxleft[i]-1]<=mxright[i]&&rightt[mxleft[i]-1]!=-1&&mxleft[i]>1){ return 1; }return 0; } int main() { cin>>n; for(ll i=1;i<n;i++){ cin>>c[i]; } for(ll i=1;i<=n;i++){ cin>>b[i]; for(ll j=0;j<b[i];j++){ ll x; cin>>x; keys[i].push_back(x); } } memset(last ,-1 ,sizeof last); for(int i=1;i<n;i++){ for(int j:keys[i]){ last[j]=i; } leftt[i]=last[c[i]]; } memset(last ,-1 ,sizeof last); for(int i=n-1;i>=1;i--){ for(int j:keys[i+1]){ last[j]=i+1; } rightt[i]=last[c[i]]; } for(ll i=1;i<=n;i++){ ll myr=i; ll myl=i; mxleft[i]=i; mxright[i]=i; while(1){ ll xx=0;ll xo=0; if(canr(i)){ xx=1; myr++; mxright[i]=myr; } if(canl(i)){ xo=1; myl--; mxleft[i]=myl; mxleft[i]=min(mxleft[i],mxleft[mxleft[i]]); mxright[i]=max(mxright[i],mxright[mxleft[i]]); } if(xo||xx){ }else{ break; } } } ll q;cin>>q; for(ll i=0;i<q;i++){ ll x,y;cin>>x>>y; //cout<<mxleft[x]<<" "<<mxright[x]; if(mxleft[x]<=y&&y<=mxright[x]){ cout<<"YES"; }else{cout<<"NO";} cout<<'\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...