This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <vector>
#include <set>
#include <cassert>
#include <algorithm>
#include <cstring>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int LOG = 19;
const int N = 1 << LOG;
const int OO = 2e9 + 10;
int n, c[N];
vector<int> klj[N];
int lst[N], lf[N], rg[N];
int L[N], R[N];
vector<int> g[N];
set<int> act, s;
int t[2 * N];
void update(int u, int w) {
u += N;
t[u] = w;
for(u >>= 1; u; u >>= 1) {
t[u] = max(t[2 * u], t[2 * u + 1]);
}
}
int query(int l, int r, int w, int u = 1, int lo = 0, int hi = N) {
if(r <= lo || hi <= l || t[u] < w) { return -1; }
if(lo + 1 == hi) { return lo; }
int mi = (lo + hi) / 2;
int res = query(l, r, w, 2 * u + 1, mi, hi);
if(res == -1) { return query(l, r, w, 2 * u, lo, mi); }
return res;
}
int main() {
scanf("%d", &n);
for(int i = 1; i < n; ++i) {
scanf("%d", c + i);
}
for(int i = 1; i <= n; ++i) {
int b; scanf("%d", &b);
for(; b--; ) {
int x; scanf("%d", &x);
klj[i].PB(x);
}
}
lf[n + 1] = lf[1] = 0;
g[0].PB(n + 1);
g[0].PB(1);
for(int i = 1; i <= n; ++i) {
if(i > 1) {
lf[i] = lst[c[i - 1]];
g[lf[i]].PB(i);
}
for(int x : klj[i]) {
lst[x] = i;
}
}
for(int i = 1; i <= n; ++i) {
lst[i] = n + 1;
}
rg[0] = rg[n] = n + 1;
for(int i = n; i >= 1; --i) {
if(i < n) {
rg[i] = lst[c[i]];
}
for(int x : klj[i]) {
lst[x] = i;
}
}
for(int x : g[0]) {
act.insert(x);
}
for(int i = 1; i <= n; ++i) {
if(act.find(i) != act.end()) {
act.erase(i);
} else if(s.find(i) != s.end()) {
s.erase(i);
}
update(i - 1, rg[i - 1]);
for(; !act.empty() && *(act.begin()) <= rg[i - 1]; act.erase(act.begin())) {
// printf("a->s %d\n", *act.begin());
s.insert(*act.begin());
}
assert(!s.empty());
R[i] = *s.begin();
L[i] = query(lf[R[i]], n + 1, R[i]);
// printf("%d %d (%d, %d)\n", L[i], R[i], lf[i], rg[i]);
for(int x : g[i]) {
act.insert(x);
}
}
int q; scanf("%d", &q);
for(; q--; ) {
int x, y; scanf("%d%d", &x, &y);
printf("%s\n", L[x] < y && y < R[x] ? "YES" : "NO");
}
return 0;
}
Compilation message (stderr)
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
49 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
long_mansion.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
51 | scanf("%d", c + i);
| ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:54:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | int b; scanf("%d", &b);
| ~~~~~^~~~~~~~~~
long_mansion.cpp:56:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | int x; scanf("%d", &x);
| ~~~~~^~~~~~~~~~
long_mansion.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
114 | int q; scanf("%d", &q);
| ~~~~~^~~~~~~~~~
long_mansion.cpp:116:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
116 | int x, y; scanf("%d%d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |