#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];
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;
while (1) {
int nr = segl.find(1, N, r, N, l);
if (!~nr) nr = N;
int nl = segr.find(1, N, 1, l, nr);
if (!~nl) nl = 1;
if (l == nl && r == nr) break;
l = nl;
r = nr;
}
}
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
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:78:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | if (ind < 0 || ind >= locs[c].size()) maxl[i] = -1;
| ~~~~^~~~~~~~~~~~~~~~~
long_mansion.cpp:85:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | if (ind >= locs[c].size()) minr[i] = N + 1;
| ~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
28116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
28116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
179 ms |
33136 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
28116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
