/** I can do this all day **/
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#define Mp make_pair
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
const int N = 5e5 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 1e9;
const int LOG = 22;
ll pw(ll a , ll b, ll M) { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }
short Ans[N];
int n, q, C[N], Z[N], X[N], Y[N], same[N << 2], seg[N << 2], lz[N << 2], last[N], nxt[N], cur[N];
vector < int > keys[N], Q[N];
void build(int v = 1, int tl = 1, int tr = n - 1)
{
lz[v] = 0;
same[v] = 0;
if(tl == tr)
{
/*if(last[tl] == -inf)
{
seg[v] = -1;
return;
}*/
seg[v] = -last[tl];
return;
}
int mid = (tl + tr) >> 1;
build(v << 1, tl, mid);
build(v << 1 | 1, mid + 1, tr);
seg[v] = max(seg[v << 1], seg[v << 1 | 1]);
}
void S(int v, int tl, int tr)
{
if(tl == tr || !lz[v]) return;
seg[v << 1] += lz[v];
seg[v << 1 | 1] += lz[v];
lz[v << 1] += lz[v];
lz[v << 1 | 1] += lz[v];
lz[v] = 0;
}
void Set(int l, int r, int x, int v = 1, int tl = 1, int tr = n - 1)
{
S(v, tl, tr);
if(l > tr || r < tl || l > r) return;
if(l <= tl && tr <= r && same[v] >= 0)
{
lz[v] += x - same[v];
seg[v] += x - same[v];
same[v] = x;
return;
}
int mid = (tl + tr) >> 1;
Set(l, r, x, v << 1, tl, mid);
Set(l, r, x, v << 1 | 1, mid + 1, tr);
seg[v] = max(seg[v << 1], seg[v << 1 | 1]);
same[v] = (same[v << 1] == same[v << 1 | 1]? same[v << 1] : -1);
}
int get(int l, int r, int v = 1, int tl = 1, int tr = n - 1)
{
S(v, tl, tr);
if(l > tr || r < tl || l > r) return -inf;
if(l <= tl && tr <= r) return seg[v];
int mid = (tl + tr) >> 1;
return max(get(l, r, v << 1, tl, mid), get(l, r, v << 1 | 1, mid + 1, tr));
}
void solve()
{
fill(cur, cur + N, -inf);
for(int i = 1; i <= n; i ++) Q[i].clear();
for(int i = 1; i <= n; i ++)
{
for(auto x : keys[i])
{
cur[x] = i;
}
/*printf("here i = %d cur : \n", i);
for(int j = 1; j <= n; j ++)
{
printf("%d ", cur[j]);
}
printf("\n");*/
if(i < n) last[i] = cur[C[i]];
}
fill(cur, cur + N, inf);
for(int i = n; i >= 1; i --)
{
for(auto x : keys[i]) cur[x] = i;
if(i > 1) nxt[i - 1] = cur[C[i - 1]];
}
/*for(int i = 1; i < n; i ++)
{
printf("i = %d last = %d nxt = %d\n", i, last[i], nxt[i]);
}*/
build();
for(int i = 1; i <= q; i ++)
{
if(X[i] < Y[i])
{
Q[X[i]].push_back(i);
}
if(X[i] == Y[i]) Ans[i] = 1;
}
/*printf("checking segment i = 0\n");
for(int i = 1; i < n; i ++) printf("%d ", get(i, i));
printf("\n");*/
for(int i = 1; i < n; i ++)
{
for(auto now : Q[i])
{
if(get(X[now], Y[now] - 1) >= 0) Ans[now] = 0;
else Ans[now] = 1;
}
Set(i + 1, min(n - 1, nxt[i] - 1), i);
/*printf("i = %d\n", i);
for(int j = 1; j < n; j ++)
{
printf("%d ", get(j, j));
}
printf("\n");*/
}
}
int main()
{
scanf("%d", &n);
for(int i = 1; i < n; i ++)
{
scanf("%d", &C[i]);
}
for(int i = 1; i <= n; i ++)
{
scanf("%d", &Z[i]);
for(int j = 1; j <= Z[i]; j ++)
{
int x;
scanf("%d", &x);
keys[i].push_back(x);
}
}
scanf("%d", &q);
for(int i = 1; i <= q; i ++)
{
scanf("%d%d", &X[i], &Y[i]);
}
solve();
reverse(C + 1, C + n);
reverse(keys + 1, keys + n + 1);
reverse(Z + 1, Z + n + 1);
for(int i = 1; i <= q; i ++)
{
X[i] = n - X[i] + 1;
Y[i] = n - Y[i] + 1;
}
solve();
for(int i = 1; i <= q; i ++)
{
if(Ans[i])
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
return 0;
}
/** test corner cases(n = 1?) watch for overflow or minus indices **/
Compilation message
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:149:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
149 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
long_mansion.cpp:152:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
152 | scanf("%d", &C[i]);
| ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:156:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
156 | scanf("%d", &Z[i]);
| ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:160:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
160 | scanf("%d", &x);
| ~~~~~^~~~~~~~~~
long_mansion.cpp:164:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
164 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
long_mansion.cpp:167:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
167 | scanf("%d%d", &X[i], &Y[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
26060 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
26060 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
715 ms |
51572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
26060 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
