Submission #1025334

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025334		1L1YA	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	645 ms	94408 KiB

long_mansion

//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);
      |                       ^~~

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