Submission #73078

#	Time	Username	Problem	Language	Result	Execution time	Memory
73078		szawinis	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	1403 ms	76400 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 19;

int n, q, C[N], lf_link[N], rg_link[N], lb[N], rb[N], tmin[N << 1], tmax[N << 1];
vector<int> ls[N];

int query_min(int l, int r) {
	int res = N;
	for(l += N, r += N+1; l < r; l >>= 1, r >>= 1) {
		if(l & 1) res = min(tmin[l++], res);
		if(r & 1) res = min(tmin[--r], res);
	}
	return res;
}

int query_max(int l, int r) {
	int res = -1;
	for(l += N, r += N+1; l < r; l >>= 1, r >>= 1) {
		if(l & 1) res = max(tmax[l++], res);
		if(r & 1) res = max(tmax[--r], res);
	}
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for(int i = 0; i < n-1; i++) cin >> C[i], --C[i];
	for(int i = 0, sz; i < n; i++) {
		cin >> sz;
		vector<int> keys(sz);
		for(int j = 0; j < sz; j++) {
			cin >> keys[j];
			--keys[j];
			ls[keys[j]].push_back(i);
		}
	}
	rg_link[0] = n;
	for(int i = 1; i < n; i++) {
		auto it = lower_bound(ls[C[i-1]].begin(), ls[C[i-1]].end(), i);
		if(ls[C[i-1]].empty() || it == ls[C[i-1]].end()) rg_link[i] = n;
		else rg_link[i] = *it;
	}
	lf_link[n-1] = -1;
	for(int i = 0; i < n-1; i++) {
		auto it = upper_bound(ls[C[i]].begin(), ls[C[i]].end(), i);
		if(ls[C[i]].empty() || it == ls[C[i]].begin()) lf_link[i] = -1;
		else lf_link[i] = *prev(it);
	}

	/* for(int type = 0; type < n; type++) { */
	/* 	cout << "type " << type << endl; */
	/* 	for(int i: ls[type]) cout << i << ' '; */
	/* 	cout << endl; */
	/* } */
	/* for(int i = 0; i < n; i++) cout << rg_link[i] << ' '; */
	/* cout << endl; */
	/* for(int i = 0; i < n; i++) cout << lf_link[i] << ' '; */
	/* cout << endl; */


	for(int i = 0; i < n; i++) tmin[N+i] = lf_link[i];
	for(int i = 0; i < n; i++) tmax[N+i] = rg_link[i];
	for(int i = N-1; i >= 1; i--) tmin[i] = min(tmin[i << 1], tmin[i << 1 | 1]);
	for(int i = N-1; i >= 1; i--) tmax[i] = max(tmax[i << 1], tmax[i << 1 | 1]);

	for(int r = 0; r < n; r++) {
		int s = lf_link[r] + 1, e = r;
		if(e-s+1 <= 0) {
			lb[r] = n;
			continue;
		}
		while(s < e) {
			int mid = s+e >> 1;
			if(query_max(lf_link[r] + 1, mid) > r) e = mid;
			else s = mid+1;
		}
		if(rg_link[s] <= r) lb[r] = n;
		else lb[r] = s;
	}
	for(int l = 0; l < n; l++) {
		int s = l, e = rg_link[l] - 1;
		if(e-s+1 <= 0) {
			rb[l] = -1;
			continue;
		}
		while(s < e) {
			int mid = s+e+1 >> 1;
			if(query_min(mid, rg_link[l] - 1) < l) s = mid;
			else e = mid-1;
		}
		if(lf_link[s] >= l) rb[l] = -1;
		else rb[l] = s;
	}

	/* for(int i = 0; i < n; i++) cout << lb[i] << ' '; */
	/* cout << endl; */
	/* for(int i = 0; i < n; i++) cout << rb[i] << ' '; */
	/* cout << endl; */

	for(int i = 0; i < n; i++) tmin[N+i] = lb[i];
	for(int i = 0; i < n; i++) tmax[N+i] = rb[i];
	for(int i = N-1; i >= 1; i--) tmin[i] = min(tmin[i << 1], tmin[i << 1 | 1]);
	for(int i = N-1; i >= 1; i--) tmax[i] = max(tmax[i << 1], tmax[i << 1 | 1]);
	cin >> q;
	while(q--) {
		int x, y;
		cin >> x >> y;
		--x, --y;
		if(x < y) {
			int res = query_min(x, y-1);
			cout << (res > x ? "YES\n" : "NO\n");
		} else {
			int res = query_max(y+1, x);
			cout << (res < x ? "YES\n" : "NO\n");
		}
	}
}

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:76:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = s+e >> 1;
              ~^~
long_mansion.cpp:90:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = s+e+1 >> 1;
              ~~~^~

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