#include <iostream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
const int INF = 1e9;
const int maxN = 500'000;
const int lgN = 19;
int N;
vector<int> C(1+maxN+1);
vector<int> key_pos_list[1+maxN+1];
vector<int> left_key_pos(1+maxN+1);
vector<int> right_key_pos(1+maxN+1);
vector<int> go_left(1+maxN+1);
vector<int> go_right(1+maxN+1);
bool queryAdj(int i, int j)
{
if(i == 0 || i == N+1) return 1;
if(j == i+1) return (go_left[i] <= right_key_pos[i]);
else if(j == i-1) return (left_key_pos[i] <= go_right[i]);
else
{
cout << "ERROR\n";
return 0;
}
}
vector<int> left_reach(1+maxN+1);
vector<int> right_reach(1+maxN+1);
struct segtree
{
int l;
int r;
int mn = 0;
int mx = 0;
segtree* left = NULL;
segtree* right = NULL;
segtree()
{
;
}
segtree(int L, int R)
{
l = L;
r = R;
if(l == r) return;
int m = (l+r)/2;
left = new segtree(l, m);
right = new segtree(m+1, r);
}
void update(int I, int V)
{
if(I < l || r < I) return;
else if(l == r)
{
mn = mx = V;
}
else
{
left->update(I, V);
right->update(I, V);
mn = min(left->mn, right->mn);
mx = max(left->mx, right->mx);
}
}
int rangemax(int L, int R)
{
if(R < l || r < L) return -INF;
else if(L <= l && r <= R)
{
return mx;
}
else
{
return max(left->rangemax(L, R), right->rangemax(L, R));
}
}
int rangemin(int L, int R)
{
if(R < l || r < L) return INF;
else if(L <= l && r <= R)
{
return mn;
}
else
{
return min(left->rangemin(L, R), right->rangemin(L, R));
}
}
};
int main()
{
//PART 0: INPUT
cin >> N;
for(int i = 1; i+1 <= N; i++)
cin >> C[i];
for(int k = 1; k <= N; k++)
key_pos_list[k].push_back(0);
for(int i = 1; i <= N; i++)
{
int B;
cin >> B;
for(int j = 1; j <= B; j++)
{
int A;
cin >> A;
key_pos_list[A].push_back(i);
}
}
for(int k = 1; k <= N; k++)
key_pos_list[k].push_back(N+1);
//PART 1: left_key_pos, right_key_pos;
left_key_pos[1] = N+1;
for(int i = 2; i <= N; i++)
{
int ind = -1;
for(int bit = lgN; bit >= 0; bit--)
{
if(ind + (1 << bit) >= key_pos_list[ C[i-1] ].size()) continue;
if(key_pos_list[ C[i-1] ][ind + (1 << bit)] >= i) continue;
ind += (1 << bit);
}
ind++;
left_key_pos[i] = key_pos_list[ C[i-1] ][ind];
}
segtree left_key_segtree(1, N);
for(int i = 1; i <= N; i++) left_key_segtree.update(i, left_key_pos[i]);
right_key_pos[N] = 0;
for(int i = N-1; i >= 1; i--)
{
int ind = -1;
for(int bit = lgN; bit >= 0; bit--)
{
if(ind + (1 << bit) >= key_pos_list[ C[i] ].size()) continue;
if(key_pos_list[ C[i] ][ind + (1 << bit)] > i) continue;
ind += (1 << bit);
}
right_key_pos[i] = key_pos_list[ C[i] ][ind];
}
segtree right_key_segtree(1, N);
for(int i = 1; i <= N; i++) right_key_segtree.update(i, right_key_pos[i]);
// PART 2: go_left, go_right;
stack<int> left_wall;
for(int i = 1; i <= N; i++)
{
// cerr << "i = " << i << '\n';
left_wall.push(i);
while(left_key_pos[ left_wall.top() ] <= i)
left_wall.pop();
go_left[i] = left_wall.top();
}
stack<int> right_wall;
for(int i = N; i >= 1; i--)
{
// cerr << "i = " << i << '\n';
right_wall.push(i);
while(right_key_pos[ right_wall.top() ] >= i)
right_wall.pop();
go_right[i] = right_wall.top();
}
// cerr << "\n\n";
// for(int i = 1; i <= N; i++) cerr << go_left[i] << ' ' << go_right[i] << '\n';
//left_wall and right_wall are now used differently.
//PART 3: left_reach
vector<int> tmp;
while(!left_wall.empty()) left_wall.pop();
for(int i = 1; i <= N; i++)
{
// cerr << "\n\n\n";
// cerr << "i = " << i << '\n';
if(queryAdj(i, i-1) == 0) //i is start of LC
{
left_reach[i] = i;
left_wall.push(i);
// cerr << "case 1: " << left_reach[i] << '\n';
}
else if(queryAdj(i+1, i) == 1) //i is in the middle of LC
{
if(queryAdj(i, i+1) == 1)
{
//compute i+1, then solve for this
tmp.push_back(i);
}
else
{
left_reach[i] = go_left[i];
for(int t: tmp) left_reach[t] = left_reach[i];
tmp.clear();
}
}
else
{
// cerr << "case 2 \n";
int curr_go_right = go_right[i];
// while(left_key_pos[ left_wall.top() ] <= go_right[i]) //do a binary search!!!!!
// left_wall.pop();
// cerr << left_wall.top() << ' ' << left_key_pos[left_wall.top()] << ' ' << curr_go_right << '\n';
for(int bit = lgN; bit >= 0; bit--)
{
int new_go_right = curr_go_right + (1 << bit);
if(new_go_right > N) continue;
if(left_wall.top() <= right_key_segtree.rangemin(i, new_go_right - 1))
curr_go_right = new_go_right;
}
while(left_key_pos[ left_wall.top() ] <= curr_go_right)
{
left_wall.pop();
for(int bit = lgN; bit >= 0; bit--)
{
int new_go_right = curr_go_right + (1 << bit);
if(new_go_right > N) continue;
if(left_wall.top() <= right_key_segtree.rangemax(i, new_go_right - 1))
curr_go_right = new_go_right;
}
// cerr << left_wall.top() << ' ' << left_key_pos[left_wall.top()] << ' ' << curr_go_right << '\n';
}
left_reach[i] = left_wall.top();
for(int t: tmp) left_reach[t] = left_reach[i];
tmp.clear();
}
}
//PART 4: right_reach
tmp.clear();
while(!right_wall.empty()) right_wall.pop();
for(int i = N; i >= 1; i--)
{
// cerr << "\n\n\n";
// cerr << "i = " << i << '\n';
if(queryAdj(i, i+1) == 0)
{
right_reach[i] = i;
right_wall.push(i);
}
else if(queryAdj(i-1, i) == 1)
{
if(queryAdj(i, i-1) == 1)
{
tmp.push_back(i);
}
else
{
right_reach[i] = go_right[i];
for(int t: tmp) right_reach[t] = right_reach[i];
tmp.clear();
}
}
else
{
int curr_go_left = go_left[i];
for(int bit = lgN; bit >= 0; bit--)
{
int new_go_left = curr_go_left - (1 << bit);
if(new_go_left < 1) continue;
if(right_wall.top() >= left_key_segtree.rangemin(new_go_left + 1, i))
curr_go_left = new_go_left;
}
// while(right_key_pos[ right_wall.top() ] >= i) //do a binary search!!!!!
// right_wall.pop();
// cerr << right_wall.top() << ' ' << right_key_pos[ right_wall.top() ] << ' ' << curr_go_left << '\n';
while(right_key_pos[ right_wall.top() ] >= curr_go_left)
{
right_wall.pop();
for(int bit = lgN; bit >= 0; bit--)
{
int new_go_left = curr_go_left - (1 << bit);
if(new_go_left < 1) continue;
if(right_wall.top() >= left_key_segtree.rangemin(new_go_left + 1, i))
curr_go_left = new_go_left;
}
// cerr << right_wall.top() << ' ' << right_key_pos[ right_wall.top() ] << ' ' << curr_go_left << '\n';
}
right_reach[i] = right_wall.top();
for(int t: tmp) right_reach[t] = right_reach[i];
tmp.clear();
}
}
// cerr << "\n\n\n";
//PART 5: QUERIES
// for(int i = 1; i <= N; i++) cerr << i << ": " << left_reach[i] << ' ' << right_reach[i] << '\n';
int Q;
cin >> Q;
for(int q = 1; q <= Q; q++)
{
int X, Y;
cin >> X >> Y;
if(left_reach[X] <= Y && Y <= right_reach[X])
cout << "YES\n";
else
cout << "NO\n";
}
}
Compilation message
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:174:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
174 | if(ind + (1 << bit) >= key_pos_list[ C[i-1] ].size()) continue;
| ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
long_mansion.cpp:192:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
192 | if(ind + (1 << bit) >= key_pos_list[ C[i] ].size()) continue;
| ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
26240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
26240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1474 ms |
51480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
26240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
