Submission #953644

#	Time	Username	Problem	Language	Result	Execution time	Memory
953644		arashMLG	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	530 ms	63404 KiB

long_mansion

#include<bits/stdc++.h>
#ifdef LOCAL
#include "Essentials/algo/debug.h"
#else
#define debug(...)    69
#define debugArr(...)  69
#endif
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("sse4")

typedef long long     ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>   pll;

const int N = 5e5 + 23;
const ll inf = 1e18;

#define F           first
#define S           second
#define pb          push_back
#define kill(x)     cout<<x<<endl, exit(0);
#define all(x)      x.begin(),x.end()
#define sz(x)       (int)x.size()
#define lc          (v << 1)
#define rc          ((v<<1) |1)

struct Seg {
	int t[N<<2];
	
	Seg() {
		fill(t,t+(N<<2),N);
	}
	
	void upd(int pos,int x,int v=1,int tl=0,int tr= N) {
		if(tr-tl == 1) {
			t[v] = min(t[v],x);
			return;
		}
		int mid=(tl+tr)/2;
		if(pos<mid)
			upd(pos,x,lc,tl,mid);
		else
			upd(pos,x,rc,mid,tr);
		t[v] = min(t[lc],t[rc]);
	}
	
	int get(int l,int r,int v=1,int tl=0,int tr= N) {
		if(l > r) return N;
		if(l == tl && r == tr-1) return t[v];
		int mid=(tl+tr)/2;
		return min( get(l,min(mid-1,r),lc,tl,mid) , get(max(l,mid),r,rc,mid,tr) );
	}
} L,R;

int n,q;
vector<int> vals[N];

bool check(int l,int r,int c) {
	if(vals[c].empty()) return false;
	if(vals[c].back() < l) return false;
	int x = *lower_bound(all(vals[c]),l);
	return x <= r;
}

int c[N];
int l[N],r[N];
int psl[N],psr[N];

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n;
	for(int i = 1; i < n ; i ++) cin>>c[i];
	for(int i = 1; i <= n ; i++) {
		int x; cin>>x;
		while(x--) {
			int y; cin>>y;
			vals[y].pb(i);
		}
	}
	// calc l
	for(int i = 1; i <= n ; i++) {
		l[i] = i;
		while(l[i] > 1) {
			if(check(l[i],i,c[l[i]-1])) {
				l[i] --;
				l[i] = min(l[i],l[l[i]]);
			} else {
				break;
			}
		}
		L.upd(i,l[i]);
	}
	// calc r
	for(int i = n ; i >= 1; i--) {
		r[i] = i;
		while(r[i] < n) {
			if(check(i,r[i],c[r[i]])) {
				r[i] ++;
				r[i] = max(r[i],r[r[i]]);
			} else {
				break;
			}
		}
		R.upd(i,-r[i]);	
	}
	vector<int> ord(n);
	iota(all(ord),1);
	//shuffle(all(ord),rng);
	for(int i : ord) {
		while(true) {
			l[i] = L.get(l[i],r[i]);
			r[i] = -R.get(l[i],r[i]);
			bool x = false,y= false;
			if(l[i] > 1) {
				x = check(l[i],r[i],c[l[i]-1]);
			}
			if(r[i] < n) {
				y = check(l[i],r[i],c[r[i]]);
			}
			if(x) {
				l[i] --;	
			}
			if(y) {
				r[i] ++;
			}
			L.upd(i,l[i]);
			R.upd(i,-r[i]);
			if(x == false && y == false) break;
		}
		debug(i,l[i],r[i]);
	}
	/*for(int i = 2; i <= n ; i++) {
		psl[i] += psl[i-1];
		psr[i] += psr[i-1];
		if(l[i] <= i-1 || check(i,r[i],c[i-1])) {
			psl[i] ++;
			debug(i,"1");
		}
		if(r[i-1] >= i || check(l[i-1],i-1,c[i-1])) {
			psr[i] ++;
			debug(i,"2");
		}
	}*/
	cin>>q;
	while(q--) {
		int x,y; cin>>x>>y;
		cout<< (y <= r[x] && y >= l[x] ? "YES" : "NO") << '\n';
	}
	return 0;
}

// Jumpsuit, Jumpsuit cover me!
// Jumpsuit, Jumpsuit cover me!

Compilation message (stderr)

long_mansion.cpp: In function 'int32_t main()':
long_mansion.cpp:5:23: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...)    69
      |                       ^~
long_mansion.cpp:132:3: note: in expansion of macro 'debug'
  132 |   debug(i,l[i],r[i]);
      |   ^~~~~

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