QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#138449 | #367. Long Mansion | jajco# | 5 | 2888ms | 4676kb | C++17 | 4.2kb | 2023-08-11 18:40:47 | 2024-07-04 01:37:05 |
Judging History
answer
#include <ios>
#include <cassert>
#include <set>
#include <vector>
#define INF (int(1e9))
#define REP(i, n) for (int i=0; i<(n); ++i)
#define FOR(i, p, n) for (int i=(p); i<(n); ++i)
#define V std::vector
typedef long long ll;
typedef V <int> vi;
typedef V <ll> vll;
typedef V <bool> vb;
struct stznaj{
vi t; // min na przedziale
int comp;
stznaj(int n, const vi &v){
comp=1;
while (comp<n)
comp<<=1;
t.resize(comp<<1, INF);
--comp;
for (size_t i=0; i<v.size(); ++i)
t[i+comp+1]=v[i];
for (int i=comp; i; --i)
t[i]=std::min(t[i<<1], t[(i<<1)+1]);
}
int znaj(int p, int k, int w){
// najmniejszy index w <p, k>, ze t[comp+i]<w
++p,++k;
int pb=-1,kb=-1;
for (p+=comp,k+=comp; p<k; p>>=1,k>>=1){
if (p&1){
if (t[p]<w&&pb<0)
pb=p;
++p;
}
if (!(k&1)){
if (t[k]<w)
kb=k;
--k;
}
}
if (p==k&&t[p]<w)
kb=p;
if (pb<0)
pb=kb;
if (pb<0)
return -1;
while (pb<=comp){
pb<<=1;
if (t[pb]>=w)
++pb;
}
return pb-comp-1;
}
};
struct prz{
int p,k;
};
int main(){
int n;
scanf("%d", &n);
vi kraw(n-1, -1); // kraw[i] to i->i+1
REP(i, n-1)
scanf("%d", &kraw[i]),--kraw[i];
V <vi> kluzb(n, vi());
V <std::set <int>> poz(n);
REP(i, n){
int l;
scanf("%d", &l);
while (l--){
int p;
scanf("%d", &p),--p;
kluzb[i].emplace_back(p);
poz[p].insert(i);
}
} // koniec wczytywania, numery zmapowane na <0,n-1>
V <prz> wyn(n);
{ // calc wynikowych przedzialow
vi lprp(n, -1),pprp(n, INF);
REP(i, n-1){
// chcemy dojsc do i krawedzia i<->i+1,
// jak daleko na prawo musimy siegac?
// i jezeli mamy <p, k>, to mozemy dojsc
// do i<p, jezeli mozemy dojsc do i+1
// oraz pprp[i]<=k
auto itr=poz[kraw[i]].upper_bound(i);
if (itr!=poz[kraw[i]].end())
pprp[i]=*itr;
}
FOR(i, 1, n){
// chcemy dojsc do i krawedzia i-1<->i,
// jak daleko na lewo musimy siegac?
// i jezeli mamy <p, k>, to mozemy dojsc
// do i>k, jezeli mozemy dojsc do i-1
// oraz lprp[i]>=p (-1 jest ok)
auto itr=poz[kraw[i-1]].lower_bound(i);
if (itr!=poz[kraw[i-1]].begin()) // czyli niepusty!
--itr,lprp[i]=*itr;
}
// teraz chcemy umiec pytac:
// "mamy <p, k>, jak daleko w prawo mozemy pojsc?"
// innymi slowy, jaki jest pierwszy >k ziom 'i'
// o lprp[i]<p? (lub ze nie istnieje)
// no to wrzucamy na st z minem na prz i tyle
stznaj st(n, lprp);
V <prz> v;
REP(i, n){
int p=i,k=st.znaj(p+1, n-1, p);
k=k<0 ? n-1 : k-1;
while (v.size()&&pprp[p-1]<=k){
// laczymy
p=std::min(v.back().p, p);
k=std::max(v.back().k, k);
v.pop_back();
// rozszerzamy
k=st.znaj(k+1, n-1, p);
k=k<0 ? n-1 : k-1;
}
prz tmp={p, k};
wyn[i]=tmp;
v.push_back(tmp);
}
}
auto brut=[&](int p, int d){
int k=p;
vb czyklu(n, 0);
auto zbierz=[&](int i){
for (int j : kluzb[i])
czyklu[j]=1;
};
zbierz(p);
while (p!=d&&k!=d){
if (p&&czyklu[kraw[p-1]]){
--p,zbierz(p);
continue;
}
if (k<n-1&&czyklu[kraw[k]]){
++k,zbierz(k);
continue;
}
break;
}
return p==d||k==d;
};
int q;
scanf("%d", &q);
while (q--){
int p,k;
scanf("%d%d", &p, &k);
--p,--k;
bool w=0;
if ((k>p&&wyn[p].k>=k)||(k<p&&wyn[p].p<=k))
w=1;
assert(brut(p, k)==w);
printf(w ? "YES\n" : "NO\n");
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 3ms
memory: 4476kb
input:
2000 10 7 7 6 12 13 3 13 10 13 10 4 1 12 13 10 10 11 14 9 2 15 15 12 6 1 7 11 14 2 4 12 15 2 4 1 7 3 8 1 10 9 10 9 1 1 3 3 10 8 14 7 15 12 4 15 13 14 13 2 6 9 12 6 12 10 11 9 15 8 15 11 2 7 9 13 14 1 1 10 14 13 13 14 15 6 8 2 1 11 11 5 4 4 13 3 6 6 12 13 1 10 6 1 15 14 6 4 7 4 13 5 1 2 11 1 8 10 7 7...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO...
result:
ok 5000 lines
Test #2:
score: 0
Accepted
time: 18ms
memory: 4164kb
input:
3000 1 4 1 3 3 4 1 2 4 1 2 3 4 2 3 4 4 1 3 1 4 2 2 4 3 3 2 1 3 2 1 3 4 4 3 2 3 2 2 4 4 1 1 3 4 1 4 1 4 1 3 3 4 1 2 1 2 4 2 1 2 1 2 3 3 3 4 2 3 2 1 2 2 1 1 1 1 1 3 3 4 1 4 4 4 4 4 1 2 4 2 2 3 3 4 2 4 3 1 2 4 1 2 1 4 1 4 4 1 3 4 3 1 2 1 3 3 2 1 2 1 2 2 4 3 3 2 4 3 3 3 1 2 1 2 4 4 1 4 1 2 1 4 4 2 2 4 2...
output:
NO YES NO NO YES NO YES YES NO YES NO NO NO NO YES YES NO YES YES YES NO NO NO YES NO NO YES YES YES NO YES YES NO NO NO NO YES NO NO YES YES NO NO YES NO YES YES YES NO NO NO NO YES NO NO YES NO NO NO NO NO NO NO YES NO NO YES NO NO NO YES NO YES NO NO NO YES YES YES YES NO YES NO NO NO NO NO NO NO...
result:
ok 5000 lines
Test #3:
score: 0
Accepted
time: 27ms
memory: 4376kb
input:
5000 1 2 1 1 2 1 2 2 1 1 1 1 1 2 1 1 1 1 2 1 1 1 1 1 1 2 2 2 1 2 1 2 2 2 1 2 2 1 1 1 2 1 2 2 2 1 2 2 2 2 2 2 2 2 1 2 1 1 2 2 2 2 1 2 2 2 1 2 2 2 1 1 1 1 1 2 2 1 2 1 2 2 1 1 2 1 1 2 1 2 2 1 2 2 1 1 2 1 1 1 2 2 2 2 2 1 1 1 1 2 2 1 2 2 1 2 1 2 2 1 2 2 1 2 2 2 2 1 1 1 1 2 1 2 1 1 1 1 2 2 2 2 1 1 2 1 1 1...
output:
YES YES NO NO NO NO YES YES YES YES YES NO NO YES YES YES YES YES YES YES YES NO NO YES NO NO YES YES YES NO YES YES YES NO YES NO NO NO YES YES NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO NO YES NO YES YES NO YES NO NO NO NO NO NO NO NO NO YES NO YES NO NO YES ...
result:
ok 5000 lines
Test #4:
score: 0
Accepted
time: 4ms
memory: 4240kb
input:
2000 583 580 319 242 218 934 584 174 18 1224 1376 793 803 842 1430 1269 1442 225 1470 376 1017 352 1081 587 689 582 492 930 918 1266 105 598 1273 343 1047 1499 247 1409 1061 1246 1248 324 1362 1254 208 1448 1438 58 1125 270 1029 355 555 212 881 1232 1093 351 1353 1436 236 498 28 635 187 1439 1257 14...
output:
NO NO NO NO NO NO NO NO NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES ...
result:
ok 5000 lines
Test #5:
score: 0
Accepted
time: 49ms
memory: 4204kb
input:
2000 32 16 47 21 12 29 8 37 50 11 22 44 1 17 3 16 19 43 27 23 32 20 28 12 30 36 12 13 24 22 30 7 45 27 33 19 3 7 3 2 33 13 3 40 26 34 42 8 25 42 28 16 48 31 46 43 45 4 37 35 37 46 43 13 3 12 40 20 8 20 47 6 19 3 16 8 21 37 24 30 44 49 34 21 18 41 23 38 13 9 39 50 40 43 17 2 15 31 43 17 8 11 4 41 35 ...
output:
YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES NO NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES YES YES YES YES YES YES YES YE...
result:
ok 5000 lines
Test #6:
score: 0
Accepted
time: 12ms
memory: 4172kb
input:
2000 393 319 1075 467 1727 78 1638 314 1362 1450 906 1073 899 1271 1520 1329 1545 170 962 1240 234 1392 593 184 1177 1387 426 130 1896 1179 407 1322 607 1589 1825 1959 1525 1442 499 1177 139 998 682 1095 1944 1626 1161 917 831 1289 553 1406 653 644 1694 1476 1342 451 52 881 1519 1465 792 1544 862 13...
output:
NO NO NO YES NO NO NO NO NO NO YES YES NO NO YES YES NO YES YES NO NO YES YES NO NO YES YES NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO YES YES NO NO YES YES NO NO YES YES NO YES YES NO NO YES YES NO NO YES YES NO NO YES ...
result:
ok 5000 lines
Test #7:
score: 0
Accepted
time: 12ms
memory: 4132kb
input:
2000 1600 1598 1596 1594 1592 1590 1588 1586 1584 1582 1580 1578 1576 1574 1572 1570 1568 1566 1564 1562 1560 1558 1556 1554 1552 1550 1548 1546 1544 1542 1540 1538 1536 1534 1532 1530 1528 1526 1524 1522 1520 1518 1516 1514 1512 1510 1508 1506 1504 1502 1500 1498 1496 1494 1492 1490 1488 1486 1484 ...
output:
YES NO NO NO NO NO NO NO NO NO NO YES NO YES YES YES NO NO NO NO NO NO YES YES YES NO NO NO YES NO NO NO NO NO NO NO NO NO NO YES NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO YES NO YES NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO YES NO NO NO NO N...
result:
ok 5000 lines
Subtask #2:
score: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Test #8:
score: 5
Accepted
time: 473ms
memory: 4136kb
input:
2000 2 6 4 1 2 7 2 2 7 6 8 4 8 7 4 5 5 10 8 7 1 1 3 1 1 5 10 2 6 1 5 10 4 5 3 1 1 9 10 9 6 2 5 2 1 10 3 8 4 3 1 3 7 6 10 1 7 1 7 1 1 6 5 10 9 8 1 10 7 5 2 9 9 8 5 3 10 7 4 3 3 9 5 8 4 3 1 6 3 4 1 4 1 9 2 5 5 6 3 10 10 7 1 4 5 4 10 1 10 2 7 4 10 10 3 2 7 4 5 8 3 6 1 6 6 8 10 3 7 8 6 9 4 1 5 8 6 8 5 3...
output:
NO YES NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO YES NO NO NO NO NO NO NO NO YES NO NO NO NO NO YES NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO N...
result:
ok 500000 lines
Test #9:
score: 0
Accepted
time: 172ms
memory: 4244kb
input:
2000 12 10 1 9 6 12 9 5 14 11 3 4 13 5 4 3 9 1 3 11 3 14 11 15 3 1 6 7 12 6 8 8 11 15 14 11 4 5 1 1 8 1 9 4 3 4 4 12 6 14 5 8 9 9 3 9 4 4 10 11 6 1 8 9 15 2 15 11 12 15 6 11 15 5 15 11 12 2 8 13 7 7 7 3 13 1 11 7 15 7 14 1 4 6 8 15 1 10 4 10 15 7 6 14 9 13 1 9 6 15 14 5 9 6 5 1 6 15 2 10 4 1 13 4 2 ...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO...
result:
ok 500000 lines
Test #10:
score: 0
Accepted
time: 1619ms
memory: 4236kb
input:
3000 4 3 4 2 2 4 1 4 4 1 1 4 3 3 3 2 2 2 2 2 4 3 2 4 2 4 2 3 3 4 1 3 2 2 2 1 3 1 3 1 1 3 2 2 1 4 4 2 1 3 3 3 2 2 2 2 3 1 3 3 4 3 3 1 4 1 2 3 3 4 4 4 3 2 3 4 2 2 1 3 4 4 1 3 3 3 1 2 2 1 4 3 4 3 4 1 1 2 1 2 1 3 1 3 3 2 3 2 4 2 4 1 3 4 1 3 3 2 2 2 4 3 3 4 1 4 2 2 4 3 1 4 1 4 2 3 2 2 3 2 2 4 4 4 3 3 1 1...
output:
NO YES NO YES YES NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO YES NO NO NO NO NO YES NO NO YES NO NO NO YES YES NO NO NO YES NO NO YES YES NO NO YES YES NO YES NO NO NO NO YES YES YES YES NO NO NO YES NO YES NO NO NO NO NO NO NO NO NO YES NO NO NO YES NO NO YES NO NO YES YES NO NO NO NO YES YES...
result:
ok 500000 lines
Test #11:
score: 0
Accepted
time: 2888ms
memory: 4676kb
input:
5000 2 1 1 2 1 1 1 1 2 2 1 1 1 2 1 2 2 1 2 1 2 2 2 2 2 1 1 1 2 1 1 2 1 2 1 1 2 1 1 1 2 2 1 1 2 1 2 1 1 2 2 1 1 1 1 2 1 1 2 1 2 2 1 1 1 1 1 1 2 1 2 2 2 1 2 1 1 2 1 1 1 1 2 1 1 1 2 1 2 2 2 2 2 2 2 2 1 1 1 2 2 1 2 1 2 1 1 1 2 1 2 1 1 2 2 1 1 1 1 2 2 1 2 2 2 1 2 1 2 1 2 2 2 1 2 2 1 2 1 2 2 1 1 2 1 2 1 1...
output:
YES NO NO YES YES YES YES NO YES YES NO NO NO NO NO NO YES YES YES YES NO NO NO YES YES YES YES NO NO NO YES YES NO NO YES NO YES YES NO YES NO NO NO YES NO NO NO YES YES NO NO YES YES NO YES YES YES NO YES YES NO YES YES NO YES NO NO NO YES YES NO YES YES NO YES YES NO NO YES NO YES NO NO NO YES NO...
result:
ok 500000 lines
Test #12:
score: 0
Accepted
time: 1369ms
memory: 4048kb
input:
1000 7 9 6 5 5 6 1 5 8 8 2 2 2 7 8 1 7 1 2 3 5 9 3 8 3 2 4 2 5 2 4 5 8 4 7 8 7 4 9 1 4 7 8 6 4 5 3 8 2 2 7 3 9 6 7 8 9 3 4 6 6 3 1 3 2 6 7 5 2 3 6 2 9 5 6 6 1 7 4 8 2 5 9 1 3 7 4 7 1 2 6 6 6 7 1 6 6 7 3 8 1 3 4 4 5 6 5 4 3 5 5 1 3 9 5 3 4 3 9 8 8 7 1 8 4 1 2 9 5 9 8 2 8 2 7 4 5 5 7 7 3 8 3 1 6 1 9 2...
output:
NO NO YES NO YES NO NO YES NO NO NO YES NO NO NO YES NO YES YES NO NO YES YES YES NO NO NO YES NO YES YES NO YES YES YES NO NO YES NO NO NO YES YES YES YES NO NO NO YES YES YES NO YES YES NO YES YES YES YES NO NO NO NO NO NO NO NO YES NO YES NO YES YES NO YES NO NO NO NO YES YES YES YES NO YES NO NO...
result:
ok 500000 lines
Test #13:
score: 0
Accepted
time: 164ms
memory: 4220kb
input:
2000 7 934 186 622 706 491 44 653 767 868 969 459 53 784 117 200 38 884 163 351 264 227 126 798 848 198 224 13 69 271 14 428 279 247 887 469 618 312 104 665 267 100 549 798 821 628 405 254 272 965 307 579 160 700 148 94 133 866 482 431 356 155 412 478 609 24 503 808 87 173 542 661 838 261 785 294 88...
output:
NO NO NO NO NO NO NO NO NO NO YES YES NO NO YES YES NO YES YES NO NO YES YES NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES NO NO YES YES NO NO YES YES NO NO YES NO NO YES YES NO NO YES YES NO NO YES NO NO YES NO N...
result:
ok 500000 lines
Test #14:
score: 0
Accepted
time: 232ms
memory: 4172kb
input:
2000 512 1028 621 489 681 387 852 266 661 1124 791 653 595 876 587 1461 1384 757 858 998 454 264 719 197 982 907 87 7 1242 879 544 1243 1062 1072 83 1069 648 1446 463 1472 455 1044 490 698 289 4 617 1459 500 947 39 272 419 859 363 247 866 1099 414 1317 715 1261 384 755 717 280 236 90 1307 410 611 45...
output:
NO NO NO NO NO YES NO NO NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES...
result:
ok 500000 lines
Test #15:
score: 0
Accepted
time: 1540ms
memory: 4100kb
input:
2000 68 76 71 44 79 9 100 63 67 57 10 37 13 18 5 38 31 2 10 3 53 52 51 3 53 31 69 9 92 86 99 97 10 32 48 92 87 11 29 87 56 16 16 83 98 29 69 81 95 31 11 5 17 27 20 85 28 21 75 100 96 33 35 28 56 70 93 69 88 56 51 80 77 58 55 92 91 97 91 53 24 52 46 15 27 100 36 45 28 96 4 24 95 27 87 50 89 78 31 53 ...
output:
NO NO YES YES NO YES YES NO NO NO YES YES YES YES YES YES NO NO YES YES NO NO YES NO NO YES YES NO NO YES YES NO YES YES NO NO YES YES NO NO YES YES YES YES YES YES NO NO YES YES YES YES NO NO YES YES NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES NO NO YES YES YES ...
result:
ok 500000 lines
Test #16:
score: -5
Time Limit Exceeded
input:
2000 29 31 20 23 48 38 11 25 19 42 50 20 1 11 28 23 40 47 16 4 22 38 38 9 18 37 30 11 28 2 13 8 34 38 11 47 12 33 7 15 21 32 4 40 50 25 47 27 14 1 15 19 18 27 23 43 16 29 47 24 29 38 37 43 39 9 46 44 41 35 2 34 35 7 41 50 4 25 22 4 23 45 21 30 40 23 29 39 5 26 11 50 14 29 33 19 30 1 23 48 17 20 28 4...
output:
YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES ...
result:
Subtask #3:
score: 0
Time Limit Exceeded
Test #27:
score: 0
Time Limit Exceeded
input:
100000 2 7 4 20 14 19 16 3 15 15 6 18 12 2 2 16 14 15 2 9 5 16 12 6 10 9 18 6 15 11 7 15 20 7 12 1 12 17 4 19 15 5 6 19 3 1 6 18 19 15 3 1 3 3 16 8 20 20 1 3 3 11 1 4 5 20 10 2 19 9 13 20 11 11 5 9 19 3 19 16 13 7 16 20 8 9 19 14 11 9 9 20 16 20 7 6 13 15 3 4 15 15 4 10 15 3 16 5 18 17 19 7 7 2 10 2...
output:
NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO...
result:
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%