Submission #526446

#	Time	Username	Problem	Language	Result	Execution time	Memory
526446		Arinoor	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	974 ms	96144 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;

#define ios				ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define all(x)			x.begin(), x.end()
#define pb				push_back
#define mp				make_pair
#define fi				first
#define se				second
#define mid				((l + r) >> 1)
#define lc				(id << 1)
#define rc				(lc | 1)
#define bug(str, x)			cerr << str << " : " << x << '\n'

typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 5e5 + 10;
const int inf = 1e9 + 10;
const int mod = 1e9 + 7;

int n, c[maxn], l[maxn], r[maxn], bound[2][maxn];
int seg[maxn << 2];
vector<int> K[maxn], ind[maxn];
set<int> S;

void add(int id, int l, int r, int p, int x){
	if(p < l or p >= r)
		return;
	if(l + 1 == r){
		seg[id] = x;
		return;
	}
	add(lc, l, mid, p, x);
	add(rc, mid, r, p, x);
	seg[id] = min(seg[lc], seg[rc]);
}

int get(int id, int l, int r, int ql, int qr, int x){
	if(qr <= l or r <= ql)
		return -1;
	if(l >= ql and r <= qr and seg[id] > x)
		return -1;
	if(l + 1 == r)
		return l;
	int R = get(rc, mid, r, ql, qr, x);
	if(~R)
		return R;
	return get(lc, l, mid, ql, qr, x);
}

void solve(int d){
	for(int i = 0; i < n - 1; i ++){
		int idx = upper_bound(all(ind[c[i]]), i) - ind[c[i]].begin();
		if(idx == ind[c[i]].size())
			r[i] = n;
		else
			r[i] = ind[c[i]][idx];
		idx --;
		if(~idx)
			l[i] = ind[c[i]][idx];
		else
			l[i] = idx;
		add(1, 0, n, i, l[i]);
	}
	for(int i = 0; i < n; i ++)
		S.insert(i);
	for(int i = n - 2; ~i; i --){
		int ind = get(1, 0, n, i + 1, r[i], i);
		if(~ind){
			while(true){
				auto it = S.upper_bound(i);
				if(it == S.end() or *it > ind)
					break;
				bound[d][*it] = i;
				S.erase(it);
			}
		}
	}
	for(int u : S)
		bound[d][u] = -1;
	//for(int i = 0; i < n; i ++)
	//	cout << d << ' ' << bound[d][i] << '\n';
}

int main(){
	ios;
	cin >> n;
	for(int i = 0; i < n - 1; i ++)
		cin >> c[i];
	for(int i = 0; i < n; i ++){
		int b;
		cin >> b;
		for(int j = 0; j < b; j ++){
			int a;
			cin >> a;
			K[i].pb(a);
			ind[a].pb(i);
		}
	}
	solve(0);
	reverse(c, c + n - 1);
	for(int i = 0; i <= n; i ++)
		ind[i].clear();
	for(int i = n - 1; ~i; i --)
		for(int u : K[i])
			ind[u].pb(n - 1 - i);
	for(int i = 0; i <= 4 * n; i ++)
		seg[i] = 0;
	S.clear();
	solve(1);
	int q;
	cin >> q;
	while(q--){
		int x, y;
		cin >> x >> y;
		x --, y --;
		if(x < y)
			cout << (n - 2 - bound[1][n - 1 - x] >= y ? "YES" : "NO") << '\n';
		else
			cout << (bound[0][x] < y ? "YES" : "NO") << '\n';
	}
}

Compilation message (stderr)

long_mansion.cpp: In function 'void solve(int)':
long_mansion.cpp:54:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   if(idx == ind[c[i]].size())
      |      ~~~~^~~~~~~~~~~~~~~~~~~

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