Submission #671439

#	Time	Username	Problem	Language	Result	Execution time	Memory
671439		flappybird	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	628 ms	98032 KiB

long_mansion

#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 505050
#define MAXS 17
#define INF 100000000000000
#define bb ' '
#define ln '\n'
#define Ln '\n'
vector<int> locs[MAX];
int C[MAX];
int minr[MAX];
int maxl[MAX];
pii intv[MAX];
map<pii, pii> mp;
struct segtree {
	int tree[MAX * 4];
	int inv;
	void init(int l, int r, int inverted = 0, int loc = 1) {
		if (l == r) {
			if (inverted) tree[loc] = minr[l];
			else tree[loc] = maxl[l];
			return;
		}
		int m = (l + r) / 2;
		init(l, m, inverted, loc * 2);
		init(m + 1, r, inverted, loc * 2 + 1);
		if (!inverted) tree[loc] = min(tree[loc * 2], tree[loc * 2 + 1]);
		else tree[loc] = max(tree[loc * 2], tree[loc * 2 + 1]);
	}
	segtree(int N, int inverted) {
		inv = inverted;
		init(1, N, inverted);
	}
	int find(int s, int e, int l, int r, int v, int loc = 1) {
		if (!inv) {
			if (e < l || r < s) return -1;
			if (tree[loc] >= v) return -1;
			if (s == e) return s;
			int m = (s + e) / 2;
			int ind = find(s, m, l, r, v, loc * 2);
			if (!~ind) return find(m + 1, e, l, r, v, loc * 2 + 1);
			else return ind;
		}
		else {
			if (e < l || r < s) return -1;
			if (tree[loc] <= v) return -1;
			if (s == e) return s;
			int m = (s + e) / 2;
			int ind = find(m + 1, e, l, r, v, loc * 2 + 1);
			if (!~ind) return find(s, m, l, r, v, loc * 2); 
			else return ind;
		}
	}
};
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N;
	cin >> N;
	int i;
	for (i = 1; i < N; i++) cin >> C[i];
	for (i = 1; i <= N; i++) {
		int s, v;
		cin >> s;
		while (s--) cin >> v, locs[v].push_back(i);
	}
	maxl[N] = -1;
	for (i = 1; i < N; i++) {
		int c = C[i];
		int ind = upper_bound(locs[c].begin(), locs[c].end(), i) - locs[c].begin();
		ind--;
		if (ind < 0 || ind >= locs[c].size()) maxl[i] = -1;
		else maxl[i] = locs[c][ind];
	}
	minr[1] = N + 1;
	for (i = N; i > 1; i--) {
		int c = C[i - 1];
		int ind = lower_bound(locs[c].begin(), locs[c].end(), i) - locs[c].begin();
		if (ind >= locs[c].size()) minr[i] = N + 1;
		else minr[i] = locs[c][ind];
	}
	segtree segl(N, 0), segr(N, 1);
	for (i = 1; i <= N; i++) {
		int l, r;
		l = r = i;
		vector<pii> ilst;
		while (1) {
			int nr = segl.find(1, N, r, N, l);
			if (!~nr) nr = N;
			if (mp.find(pii(l, nr)) != mp.end()) {
				tie(l, r) = mp[pii(l, nr)];
				break;
			}
			int nl = segr.find(1, N, 1, l, nr);
			if (!~nl) nl = 1;
			ilst.emplace_back(nl, nr);
			if (l == nl && r == nr) break;
			if (mp.find(pii(nl, nr)) != mp.end()) {
				tie(l, r) = mp[pii(nl, nr)];
				break;
			}
			l = nl;
			r = nr;
		}
		intv[i] = { l, r };
		for (auto l : ilst) mp[l] = intv[i];
	}
	int Q;
	cin >> Q;
	while (Q--) {
		int a, b;
		cin >> a >> b;
		if (intv[a].first <= b && b <= intv[a].second) cout << "YES" << ln;
		else cout << "NO" << ln;
	}
}

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   if (ind < 0 || ind >= locs[c].size()) maxl[i] = -1;
      |                  ~~~~^~~~~~~~~~~~~~~~~
long_mansion.cpp:86:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   if (ind >= locs[c].size()) minr[i] = N + 1;
      |       ~~~~^~~~~~~~~~~~~~~~~

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