This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'
int n , q , in[500000][2];
vector<int> inxs[500000];
int seg[2000001][2] , seginf[2000001][2];
void init(){
for(int i = 0 ; i < n ; i++){
if(in[i][0] != -1){
auto itr = lb(inxs[in[i][0]].bg() , inxs[in[i][0]].end() , i);
if(itr == inxs[in[i][0]].bg()) in[i][0] = -1;
else in[i][0] = *(--itr);
}
if(in[i][1] != -1){
auto itr = ub(inxs[in[i][1]].bg() , inxs[in[i][1]].end() , i);
if(itr == inxs[in[i][1]].end()) in[i][1] = n;
else in[i][1] = *(itr);
}
}
}
void buildSeg(int l = 0 , int r = n - 1 , int i = 1){
seginf[i][0] = l , seginf[i][1] = r;
if(l == r){
seg[i][0] = in[l][0];
seg[i][1] = in[l][1];
}else{
int c = (r + l - 1) >> 1;
buildSeg(l , c , i << 1) , buildSeg(c + 1 , r , (i << 1) | 1);
seg[i][0] = min(seg[i << 1][0] , seg[(i << 1) | 1][0]);
seg[i][1] = max(seg[i << 1][1] , seg[(i << 1) | 1][1]);
}
}
int getSeg(int l , int r , int i , int md){
if(seginf[i][0] >= l and seginf[i][1] <= r) return seg[i][md];
if(seginf[i][1] >= l and seginf[i][0] <= r){
if(md == 0) return min(getSeg(l , r , i << 1 , md) , getSeg(l , r , (i << 1) | 1 , md));
return max(getSeg(l , r , i << 1 , md) , getSeg(l , r , (i << 1) | 1 , md));
}
if(md == 0) return n;
return -1;
}
int bsmx(int l , int r){
int i = l , j = r;
l--;
while(r - l - 1 > 1){
int c = (r + l + 1) >> 1;
if(getSeg(i , c , 1 , 1) >= j) r = c;
else l = c - 1;
}
if(r - l - 1 == 1 and getSeg(i , r - 1 , 1 , 1) >= j) return r - 1;
return r;
}
int bsmn(int l , int r){
int i = l , j = r;
r++;
while(r - l - 1 > 1){
int c = (r + l + 1) >> 1;
if(getSeg(c , j , 1 , 0) <= i) l = c - 1;
else r = c;
}
if(r - l - 1 == 1 and getSeg(l + 1 , j , 1 , 0) <= i) return l + 1;
return l;
}
void f(){
buildSeg();
for(int i = 0 ; i < n ; i++){
if(in[i][0] != -1){
in[i][0] = bsmx(in[i][0] , i);
}
if(in[i][1] != n){
in[i][1] = bsmn(i , in[i][1]);
}
}
buildSeg();
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
in[0][0] = -1 , in[n - 1][1] = n;
for(int i = 1 ; i < n ; i++){
int d;
cin >> d;
in[i - 1][1] = d - 1 , in[i][0] = d - 1;
}
for(int i = 0 ; i < n ; i++){
int b;
cin >> b;
for(int j = 0 ; j < b ; j++){
int d;
cin >> d;
inxs[d - 1].pb(i);
}
}
init() , f();
cin >> q;
for(int i = 0 ; i < q ; i++){
int v , u;
cin >> v >> u;
v-- , u--;
if(v < u){
int d = getSeg(v + 1 , u , 1 , 0);
if(d >= v) cout << "YES\n";
else cout << "NO\n";
}else{
int d = getSeg(u , v - 1 , 1 , 1);
if(d <= v) cout << "YES\n";
else cout << "NO\n";
}
}
}
# | 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... |