Submission #1025334

#TimeUsernameProblemLanguageResultExecution timeMemory
10253341L1YALong Mansion (JOI17_long_mansion)C++17
100 / 100
645 ms94408 KiB
//1L1YA #include<bits/stdc++.h> using namespace std; //#pragma GCC optimize ("O3,unrool-loops") //#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") typedef long long ll; typedef pair<ll,ll> pll; typedef pair<int,int> pii; #define Pb push_back #define F first #define S second #define endl '\n' #define sep ' ' #define all(x) x.begin(),x.end() #define al(x,n) x+1,x+n+1 #define SZ(x) ((int)x.size()) #define lc (id<<1) #define rc (lc|1) #define mid (l+r>>1) #define dokme(x) cout << x << endl, exit(0) #define sik(x) cout << x << endl;continue; #define FastIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define FileIO freopen("input.txt","r",stdin);freopen("output.txt","w",stdout); mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll oo=1e18; const int mod=1e9+7; const int inf=1e9+111; const int N=5e5+11; const int lg=23; int n,m,q,a[N],l[N],r[N],lst[N]; vector<int> vc[N],vec[N]; pii val[N],seg[N<<2]; void build(int id=1,int l=1,int r=n+1){ seg[id]={1,n}; if(r-l==1) return; build(lc,l,mid); build(rc,mid,r); } void update(int ql,int qr,pii val,int id=1,int l=1,int r=n+1){ if(qr<=l || ql>=r) return; if(ql<=l && r<=qr){ seg[id].F=max(seg[id].F,val.F); seg[id].S=min(seg[id].S,val.S); return; } update(ql,qr,val,lc,l,mid); update(ql,qr,val,rc,mid,r); } pii get(int pos,int id=1,int l=1,int r=n+1){ if(r-l==1) return seg[id]; pii p; if(pos<mid) p=get(pos,lc,l,mid); else p=get(pos,rc,mid,r); return {max(p.F,seg[id].F),min(p.S,seg[id].S)}; } int main(){ FastIO cin >> n; for(int i=1;i<n;i++) cin >> a[i]; for(int i=1;i<=n;i++){ cin >> m; for(int j=1;j<=m;j++){ int x;cin >> x; vc[i].Pb(x); } } for(int i=1;i<n;i++){ for(int j: vc[i]) lst[j]=i; l[i]=lst[a[i]]; } fill(lst,lst+n+1,n+1); for(int i=n;i>1;i--){ for(int j: vc[i]) lst[j]=i; r[i-1]=lst[a[i-1]]; vec[r[i-1]].Pb(i); } build(); set<int> st; for(int i=0;i<=n;i++){ for(int j: vec[i]) st.erase(j); if(SZ(st)){ auto it=st.upper_bound(l[i]); if(it!=st.end()) update(*it,i+1,{1,i}); } st.insert(i+1); } st.clear(); for(int i=0;i<=n+1;i++) vec[i].clear(); for(int i=1;i<n;i++) vec[l[i]].Pb(i); r[0]=n+1; for(int i=n+1;i;i--){ for(int j: vec[i]) st.erase(j); if(SZ(st)){ auto it=st.lower_bound(r[i-1]); if(it--!=st.begin()) update(i,(*it)+1,{i,n}); } st.insert(i-1); } for(int i=1;i<=n;i++) val[i]=get(i); cin >> q; while(q--){ int x,y; cin >> x >> y; if(y>=val[x].F && y<=val[x].S) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }

Compilation message (stderr)

long_mansion.cpp: In function 'void build(int, int, int)':
long_mansion.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
long_mansion.cpp:44:16: note: in expansion of macro 'mid'
   44 |     build(lc,l,mid);
      |                ^~~
long_mansion.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
long_mansion.cpp:45:14: note: in expansion of macro 'mid'
   45 |     build(rc,mid,r);
      |              ^~~
long_mansion.cpp: In function 'void update(int, int, pii, int, int, int)':
long_mansion.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
long_mansion.cpp:55:27: note: in expansion of macro 'mid'
   55 |     update(ql,qr,val,lc,l,mid);
      |                           ^~~
long_mansion.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
long_mansion.cpp:56:25: note: in expansion of macro 'mid'
   56 |     update(ql,qr,val,rc,mid,r);
      |                         ^~~
long_mansion.cpp: In function 'pii get(int, int, int, int)':
long_mansion.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
long_mansion.cpp:62:12: note: in expansion of macro 'mid'
   62 |     if(pos<mid) p=get(pos,lc,l,mid);
      |            ^~~
long_mansion.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
long_mansion.cpp:62:32: note: in expansion of macro 'mid'
   62 |     if(pos<mid) p=get(pos,lc,l,mid);
      |                                ^~~
long_mansion.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
long_mansion.cpp:63:23: note: in expansion of macro 'mid'
   63 |     else p=get(pos,rc,mid,r);
      |                       ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...