#include<iostream>
#include<map>
#include<vector>
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std ;
const int N = (1 << 19), NS = 5e3 ;
bool flag, us[NS + 1][NS + 1] ;
int n, q, sm, c[N + 1] ;
vector<int> sg[2 * N + 1], sg_b[2 * N + 1] ;
vector<int> nul, ks[N + 1] ;
map<int, int> ch, null ;
void bfs(int city)
{
ch = null ;
bool abu = 1 ;
int l = city, r = city ;
for(int i : ks[city])
ch[i] = 1 ;
us[city][city] = 1 ;
while(abu)
{
abu ^= 1 ;
if(l > 1 && ch[c[l - 1]])
{
l-- ;
for(int i : ks[l])
ch[i] = 1 ;
us[city][l] = 1 ;
abu |= 1 ;
}
if(r < n && ch[c[r]])
{
abu |= 1 ;
r++ ;
for(int i : ks[r])
ch[i] = 1 ;
us[city][r] = 1 ;
}
}
}
vector<int> mrg(vector<int> a, vector<int> b)
{
if(!a.size() || !b.size())
{
if(a.size())
return a ;
else
return b ;
}
int uk1 = 0, uk2 = 0 ;
vector<int> c ;
while(c.size() < 20 && (uk1 < a.size() || uk2 < b.size()))
{
int mn = 21 ;
if(uk1 < a.size())
mn = min(mn, a[uk1]) ;
if(uk2 < b.size())
mn = min(mn, b[uk2]) ;
if(!c.size() || c.back() != mn)
c.push_back(mn) ;
if(uk1 < a.size() && a[uk1] == mn)
uk1++ ;
else
uk2++ ;
}
return c ;
}
void build()
{
for(int i = 0 ; i < N ; i++)
{
sg[i + N].push_back(c[i]) ;
sg_b[i + N] = ks[i] ;
}
for(int i = N - 1 ; i > 0 ; i--)
{
sg[i] = mrg(sg[i * 2], sg[i * 2 + 1]) ;
sg_b[i] = mrg(sg_b[i * 2], sg_b[i * 2 + 1]) ;
}
}
vector<int> get_all(int l1, int r1)
{
l1 += N ;
r1 += N ;
vector<int> res ;
while(l1 <= r1)
{
if(l1 % 2 == 1)
res = mrg(res, sg[l1++]) ;
if(r1 % 2 == 0)
res = mrg(res, sg[r1--]) ;
l1 >>= 1 ;
r1 >>= 1 ;
}
return res ;
}
vector<int> get_all_b(int l1, int r1)
{
l1 += N ;
r1 += N ;
vector<int> res ;
while(l1 <= r1)
{
if(l1 % 2 == 1)
res = mrg(res, sg_b[l1++]) ;
if(r1 % 2 == 0)
res = mrg(res, sg_b[r1--]) ;
l1 >>= 1 ;
r1 >>= 1 ;
}
return res ;
}
signed main()
{
ios_base::sync_with_stdio( 0 ) ;
cin.tie( 0 ) ;
cout.tie( 0 ) ;
cin >> n ;
for(int i = 1 ; i < n ; i++)
{
cin >> c[i] ;
if(c[i] > 20)flag = 1 ;
}
for(int i = 1 ; i <= n ; i++)
{
int b ;
cin >> b ;
sm += b ;
for(int j = 1 ; j <= b ; j++)
{
int a ;
cin >> a ;
if(a > 20)flag = 1 ;
ks[i].push_back(a) ;
}
}
cin >> q ;
if(n <= 100000 && !flag)
{
build() ;
while(q--)
{
bool abu[21] = {} ;
bool fl = 1 ;
int x, y ;
cin >> x >> y ;
int lf = x, rg = x ;
for(int j : ks[x])
abu[j] = 1 ;
while(fl)
{
fl ^= 1 ;
vector<int> vl, vr ;
int l = 0, r = lf ;
while(l + 1 < r)
{
bool check = 0 ;
int mid = (l + r) >> 1 ;
vl = get_all(mid, lf - 1) ;
for(int j : vl)
{
if(!abu[j])check = 1 ;
}
if(check)
l = mid ;
else
r = mid ;
}
if(r < lf)
{
vl = get_all_b(r, lf - 1) ;
for(int j : vl)
abu[j] = 1 ;
lf = r ;
fl = 1 ;
}
l = rg - 1, r = n ;
while(l + 1 < r)
{
bool check = 0 ;
int mid = (l + r) >> 1 ;
vr = get_all(rg, mid) ;
for(int j : vr)
if(!abu[j])check = 1 ;
if(check)
r = mid ;
else
l = mid ;
}
if(l >= rg)
{
vr = get_all_b(rg + 1, l + 1) ;
for(int j : vr)
abu[j] = 1 ;
fl = 1 ;
rg = l + 1 ;
}
}
if(lf <= y && y <= rg)
cout << "YES\n" ;
else
cout << "NO\n" ;
}
return 0 ;
}
if(n <= 5000 && sm <= 5000)
{
for(int i = 1 ; i <= n ; i++)
bfs(i) ;
for(int i = 1 ; i <= q ; i++)
{
int x, y ;
cin >> x >> y ;
if(us[x][y])
cout << "YES\n" ;
else
cout << "NO\n" ;
}
return 0 ;
}
return 0 ;
}
Compilation message
long_mansion.cpp: In function 'std::vector<int> mrg(std::vector<int>, std::vector<int>)':
long_mansion.cpp:53:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | while(c.size() < 20 && (uk1 < a.size() || uk2 < b.size()))
| ~~~~^~~~~~~~~~
long_mansion.cpp:53:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | while(c.size() < 20 && (uk1 < a.size() || uk2 < b.size()))
| ~~~~^~~~~~~~~~
long_mansion.cpp:56:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | if(uk1 < a.size())
| ~~~~^~~~~~~~~~
long_mansion.cpp:58:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | if(uk2 < b.size())
| ~~~~^~~~~~~~~~
long_mansion.cpp:62:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | if(uk1 < a.size() && a[uk1] == mn)
| ~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
225 ms |
95000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
225 ms |
95000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3080 ms |
113048 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
225 ms |
95000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
