QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#763403 | #6332. Two Currencies | cocoa_chan | 10 | 3720ms | 130356kb | C++14 | 4.0kb | 2024-11-19 20:05:10 | 2024-11-19 20:05:10 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll siz=262144;
ll n,m,i,j,k,l,r,x,y,z,w,s,t,a[1100000],le[1100000],ri[1100000],seg[3][1100000],silver[1100000],gold[1100000],ednum[1100000],stnum[1100000],st[1100000],ed[1100000],h[1100000],b[1100000],q,sparse[21][110000],ee,mid;
vector<ll> v[1100000];
vector<ll> u[1100000];
pair<ll,ll> p[1100000],pp[1100000];
void dfs(ll x,ll y)
{
sparse[0][x]=y;
h[x]=h[y]+1;
t++;
stnum[x]=t;
ll i;
for(i=0;i<v[x].size();i++)
{
if(v[x][i]==y)
continue;
dfs(v[x][i],x);
}
t++;
ednum[x]=t;
}
void Clear()
{
ll i;
for(i=0;i<550000;i++)
{
seg[1][i]=0;
seg[2][i]=0;
}
}
void f(ll idx,ll z)
{
seg[idx][z]=seg[idx][z*2]+seg[idx][z*2+1];
if(z==1)
return;
f(idx,z/2);
}
ll g(ll idx,ll x,ll y,ll z)
{
if(l>y||x>r)
return 0;
if(l<=x&&y<=r)
return seg[idx][z];
return g(idx,x,(x+y)/2,z*2)+g(idx,(x+y)/2+1,y,z*2+1);
}
void add(ll idx,ll x,ll y,ll z)
{
if(h[x]>h[y])
swap(x,y);
seg[idx][stnum[y]+siz-1]+=z;
f(idx,(stnum[y]+siz-1)/2);
seg[idx][ednum[y]+siz]-=z;
f(idx,(ednum[y]+siz)/2);
}
ll lca(ll x,ll y)
{
if(h[x]>h[y])
swap(x,y);
ll w=h[y]-h[x],z=0;
while(w)
{
if(w&1)
{
y=sparse[z][y];
}
w>>=1;
z++;
}
if(x==y)
return x;
z=18;
while(z>=0)
{
if(sparse[z][x]!=sparse[z][y])
{
x=sparse[z][x];
y=sparse[z][y];
}
z--;
}
return sparse[0][x];
}
ll query(ll idx,ll x,ll y)
{
if(h[x]<h[y])
swap(x,y);
ll z=lca(x,y);
//printf("(%lld,%lld,%lld)\n",x,y,z);
ll s=0;
l=1;
r=stnum[x];
s+=g(idx,1,siz,1);
//printf("(%lld)",s);
l=1;
r=stnum[y];
s+=g(idx,1,siz,1);
//printf("(%lld)",s);
l=1;
r=stnum[z];
s-=2*g(idx,1,siz,1);
//printf("(%lld)",s);
return s;
}
int main()
{
scanf("%lld %lld %lld",&n,&m,&q);
for(i=1;i<n;i++)
{
scanf("%lld %lld",&x,&y);
p[i]={x,y};
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,0);
for(j=1;j<=20;j++)
{
for(i=1;i<=n;i++)
{
sparse[j][i]=sparse[j-1][sparse[j-1][i]];
}
}
for(i=1;i<=m;i++)
{
scanf("%lld %lld",&x,&y);
pp[i]={y,x};
}
sort(pp+1,pp+m+1);
for(i=1;i<=m;i++)
swap(pp[i].first,pp[i].second);
for(i=1;i<=q;i++)
{
scanf("%lld %lld %lld %lld",&x,&y,&z,&w);
le[i]=0;
ri[i]=m;
st[i]=x;
ed[i]=y;
gold[i]=z;
silver[i]=w;
}
for(ee=0;ee<18;ee++)
{
//printf("!");
Clear();
for(i=1;i<=m;i++)
{
add(1,p[pp[i].first].first,p[pp[i].first].second,1);
}
for(i=0;i<=m+1;i++)
{
u[i].clear();
}
for(i=1;i<=q;i++)
{
mid=(le[i]+ri[i]+1)/2;
u[mid].push_back(i);
}
for(i=0;i<=m;i++)
{
if(i)
{
add(2,p[pp[i].first].first,p[pp[i].first].second,pp[i].second);
add(1,p[pp[i].first].first,p[pp[i].first].second,-1);
}
for(auto xx:u[i])
{
x=st[xx];
y=ed[xx];
b[xx]=query(1,x,y);
s=query(2,x,y);
//printf("(%lld,%lld,%lld:%lld)\n",i,x,y,s);
if(silver[xx]<s)
{
ri[xx]=i-1;
}
else
{le[xx]=i;
}
}
}
}
for(i=1;i<=q;i++)
{
if(gold[i]-b[i]<0)
printf("-1\n");
else
printf("%lld\n",gold[i]-b[i]);
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 42ms
memory: 88720kb
input:
1831 1865 1153 832 1698 1672 1619 634 920 328 1244 571 1279 1673 1815 1098 92 1320 432 244 636 991 1446 308 569 1118 1356 1733 71 497 1679 1699 635 1254 1295 853 345 364 1396 1183 1134 524 1557 1642 1262 1767 459 918 794 1644 539 902 1046 334 1789 1691 1548 1298 520 1763 216 1161 1065 682 1167 1282 ...
output:
378730605 649537044 339843141 362013697 600127619 123276007 749019778 22 30 54569538 -1 26669081 33 255375699 0 7 8 -1 427653834 2 9 19 7 9 -1 8 6 265022184 218253041 -1 24 849614439 9 29092527 539604026 0 6 -1 6 -1 12 8 -1 22 -1 13 11 26 7 -1 2 0 546008661 4 6 86261072 -1 448122840 873577464 -1 0 1...
result:
ok 1153 numbers
Test #2:
score: 10
Accepted
time: 53ms
memory: 74800kb
input:
1942 1832 1894 1076 1725 1111 725 1093 19 921 1759 1917 1017 1854 724 901 1713 58 1482 1469 134 1463 1030 159 162 3 570 781 1533 64 1043 1693 894 329 1075 252 1727 1579 213 1051 419 67 80 351 1739 990 313 1545 94 680 649 1769 140 678 1755 602 17 598 476 586 509 1321 1535 402 949 1135 1196 1668 985 1...
output:
290930763 222025343 905421625 3 2 691499099 9 -1 -1 923482030 11 11 22 10 1 5 12 13 230762895 808118430 470508163 -1 -1 5 769521091 1 649347743 867764525 3 4 9 -1 635895869 518880732 -1 161787337 812530072 -1 7 8 25 -1 5 6 0 3 655886721 576512193 3 440416008 7 8 -1 -1 -1 11 11 3 -1 418197782 5773691...
result:
ok 1894 numbers
Test #3:
score: 10
Accepted
time: 46ms
memory: 90620kb
input:
1259 1420 1830 767 33 409 881 144 630 754 665 98 954 1133 741 163 1011 351 474 1165 168 213 70 1257 801 654 727 336 1238 147 756 956 639 540 671 1049 837 967 768 275 565 480 791 922 739 504 906 281 683 1069 1019 1195 716 851 45 119 515 1226 997 153 1163 1180 333 941 649 32 1199 1118 699 144 181 675 ...
output:
20 293315087 17 214464390 1 7 1 1 463782411 193462252 -1 264243615 238908207 -1 578800563 1 17 20 2 -1 490218156 4 2587714 12 17716886 171554130 22 10 10 283890617 3 32583568 1 1 3 334255184 7 6 2 3 518826413 610186572 -1 3 297569392 -1 -1 0 -1 4 987836934 0 35 315447009 10 13 14 -1 -1 711900410 19 ...
result:
ok 1830 numbers
Test #4:
score: 10
Accepted
time: 53ms
memory: 90832kb
input:
2000 2000 2000 439 1912 92 340 1771 416 403 550 885 1093 1664 1308 124 506 1535 1848 1806 1245 1057 791 805 1930 1607 1456 1795 1409 969 1527 471 1553 1794 1721 1967 829 979 243 1360 295 392 911 963 1566 1815 663 356 770 23 924 964 1883 1668 1499 1514 927 412 1764 1270 418 649 369 1828 1958 687 428 ...
output:
16 18 6 -1 7 -1 14 0 17 10 8 16 4 -1 11 9 6 7 9 27 0 17 1 -1 22 29 -1 -1 -1 5 0 3 -1 -1 4 22 4 1 5 7 15 8 14 -1 7 11 9 1 12 17 -1 10 15 5 17 -1 1 1 18 -1 13 7 -1 4 18 2 13 -1 -1 5 13 3 5 -1 13 0 13 5 5 4 -1 22 11 -1 6 20 10 9 -1 -1 2 24 1 -1 0 3 1 4 -1 2 -1 14 15 6 -1 9 17 3 4 4 10 11 -1 2 9 -1 -1 1...
result:
ok 2000 numbers
Test #5:
score: 10
Accepted
time: 52ms
memory: 90792kb
input:
2000 2000 2000 1908 583 1115 1046 1858 74 587 1569 549 1911 1350 1887 1101 277 396 1518 569 1528 988 150 1559 1967 683 484 1569 1050 1864 1335 1218 52 1600 925 1047 90 1870 1263 157 185 141 1388 316 102 1903 1907 124 1179 1172 1928 1730 1398 1226 1976 450 657 1830 821 275 459 1382 634 1458 297 1212 ...
output:
24 2 1 -1 8 -1 -1 11 4 15 21 6 2 -1 2 3 -1 18 -1 0 -1 6 -1 21 -1 17 -1 9 -1 -1 -1 6 -1 3 15 -1 10 -1 7 -1 0 6 14 8 1 15 5 -1 -1 7 -1 -1 5 0 20 7 -1 -1 7 7 5 -1 11 3 -1 2 16 -1 -1 8 0 5 7 -1 9 14 2 2 11 -1 10 3 11 -1 6 12 12 34 8 -1 6 -1 -1 12 -1 2 4 2 19 -1 -1 0 8 -1 13 -1 0 2 14 29 25 3 1 13 15 13 ...
result:
ok 2000 numbers
Test #6:
score: 10
Accepted
time: 51ms
memory: 72700kb
input:
2000 2000 2000 1532 700 306 1701 1697 1130 2000 1322 661 231 77 683 1773 1224 634 1533 155 1831 1418 1618 1945 1255 607 1006 432 20 298 1250 1180 1430 1796 142 144 1379 1713 583 1583 80 1552 1280 1327 1705 1861 517 337 725 669 303 1974 628 1176 829 1258 251 172 1757 1737 1486 1585 597 1440 1552 1610...
output:
1 20 -1 -1 -1 7 0 0 -1 13 7 6 2 -1 5 6 8 -1 1 7 11 -1 -1 -1 6 8 -1 -1 2 -1 6 10 10 -1 16 16 -1 -1 0 8 -1 -1 12 15 8 10 1 23 7 9 6 3 14 8 0 5 7 3 8 12 -1 10 1 4 -1 24 -1 22 -1 0 10 0 -1 1 23 2 2 -1 1 13 3 4 5 -1 14 4 7 -1 2 11 9 13 15 9 4 -1 7 6 3 16 1 0 7 5 11 1 32 3 26 -1 -1 8 11 3 4 2 13 9 10 -1 2...
result:
ok 2000 numbers
Test #7:
score: 10
Accepted
time: 54ms
memory: 72832kb
input:
2000 2000 2000 241 900 1930 1379 1438 670 667 1290 733 1932 1295 1721 855 1330 850 601 1751 716 1081 1571 1983 717 1269 1751 1288 69 333 714 1202 600 1447 576 1745 383 151 1669 1565 1814 689 1870 648 1217 1529 1190 957 1840 1130 1713 1660 558 102 1316 1784 973 1057 1072 113 1883 766 1033 182 326 121...
output:
7 11 31 -1 28 25 25 7 4 -1 -1 -1 -1 19 -1 9 2 0 7 13 1 17 4 4 59 17 2 8 36 0 0 10 2 -1 9 14 13 2 1 -1 11 7 -1 -1 3 0 18 -1 0 8 1 29 24 15 6 13 29 10 15 3 3 6 3 43 -1 1 -1 -1 5 17 -1 3 5 14 10 12 16 4 15 7 9 18 0 14 6 11 -1 9 15 -1 -1 21 0 20 15 11 14 18 32 -1 13 6 -1 -1 23 11 -1 13 -1 6 5 -1 12 7 1 ...
result:
ok 2000 numbers
Test #8:
score: 10
Accepted
time: 62ms
memory: 66716kb
input:
2000 2000 2000 1453 1310 1106 1265 57 520 1265 300 461 1199 1805 139 62 628 1923 1503 703 1334 10 141 942 1165 1850 983 475 1937 1821 954 1771 752 825 1914 1534 944 452 1551 1532 1010 724 1212 323 1637 1159 65 312 621 1633 581 1096 1964 889 1083 857 1590 1367 1329 30 36 286 507 174 1681 413 840 592 ...
output:
4 -1 -1 -1 9 14 5 6 22 -1 -1 34 20 -1 35 0 16 9 7 14 -1 9 13 0 18 6 5 -1 5 15 6 2 18 5 18 8 7 10 13 12 20 10 -1 -1 2 9 2 -1 -1 2 6 29 11 27 10 2 4 3 22 7 1 9 20 11 1 -1 2 8 16 13 -1 -1 8 21 5 -1 0 14 -1 9 9 5 21 3 8 13 24 -1 13 12 2 -1 18 27 3 9 -1 10 12 -1 9 -1 -1 4 -1 10 12 8 11 -1 6 5 5 7 15 0 -1...
result:
ok 2000 numbers
Test #9:
score: 10
Accepted
time: 50ms
memory: 66764kb
input:
2000 2000 2000 322 586 1516 535 436 1706 471 1457 1013 1890 787 511 1276 49 43 1558 1869 822 1599 1671 1139 1791 1385 720 522 524 1537 1720 1641 570 1987 1657 1244 1000 266 1703 1987 1586 134 89 1226 1343 1316 823 1505 890 123 662 1154 607 1349 1847 1379 1072 1483 414 97 1549 861 869 1807 169 794 82...
output:
1710 220 -1 447 10 1456 480 78 411 -1 81 274 -1 -1 184 1889 73 -1 -1 -1 45 -1 184 697 251 555 149 27 20 503 213 181 490 1290 156 108 -1 -1 138 512 128 1013 378 968 -1 52 764 404 274 -1 119 2178 -1 -1 1667 -1 845 235 1358 37 201 -1 -1 1199 1504 -1 309 1040 1438 -1 80 -1 -1 1346 -1 352 683 1017 -1 12 ...
result:
ok 2000 numbers
Test #10:
score: 10
Accepted
time: 51ms
memory: 72780kb
input:
2000 2000 2000 1564 687 910 825 141 1628 1559 423 968 936 621 1039 313 1740 910 23 1665 1510 807 1509 218 992 1668 37 250 1361 1924 1002 1031 406 177 86 1250 1886 1904 534 801 524 1902 484 1527 520 1210 115 652 1086 1413 239 1223 966 1985 165 760 554 1357 751 1232 913 513 1189 1433 474 480 1782 464 ...
output:
1360 -1 69 320 398 486 853 300 579 600 956 1447 142 83 115 305 53 864 83 24 447 190 -1 1212 36 128 155 -1 -1 245 388 -1 -1 1215 38 37 3 3 805 610 70 -1 380 146 157 87 -1 1057 1525 -1 423 559 5 204 517 723 63 1442 70 110 441 15 1116 -1 -1 203 -1 1044 -1 89 119 524 1080 1648 213 395 344 1095 788 164 8...
result:
ok 2000 numbers
Test #11:
score: 10
Accepted
time: 51ms
memory: 66728kb
input:
2000 2000 2000 1509 92 1257 1098 1768 1647 359 654 1743 1459 968 1397 1010 58 1725 70 1808 22 1262 1492 118 191 1455 618 827 1723 1775 246 14 824 325 1660 1821 1246 855 246 1189 1011 926 310 782 811 190 8 1949 1001 1210 1383 884 23 408 1294 221 312 1056 1294 1731 1698 1521 1069 248 1514 1747 153 152...
output:
-1 262 251 -1 18 164 268 -1 27 246 50 120 331 65 -1 49 321 512 7 14 227 151 110 0 343 1 68 188 196 -1 -1 164 110 134 241 379 39 473 16 155 58 454 29 -1 -1 621 126 392 8 -1 364 539 595 507 188 -1 174 337 -1 526 493 323 162 104 -1 256 220 -1 257 307 146 494 -1 256 65 10 170 -1 -1 142 39 34 459 158 490...
result:
ok 2000 numbers
Test #12:
score: 10
Accepted
time: 47ms
memory: 72620kb
input:
2000 2000 2000 598 1485 5 1107 1741 985 819 1339 126 1615 712 725 121 1355 821 1194 1924 1438 175 70 1846 1508 216 741 1624 1154 891 394 1993 45 1878 269 1931 1443 385 669 576 1307 1823 1002 1349 1641 808 1086 397 1906 508 1910 122 1973 1913 972 291 900 1865 88 553 202 854 1437 482 554 1398 868 347 ...
output:
300 208 34 35 259 65 -1 76 32 333 362 250 12 -1 75 335 -1 12 -1 468 -1 -1 -1 11 123 193 -1 523 79 133 139 456 -1 366 -1 362 -1 81 357 140 115 452 4 104 -1 78 160 110 376 52 120 231 336 329 359 -1 94 -1 19 -1 50 119 -1 67 183 135 124 90 352 82 359 -1 370 667 103 28 207 50 132 279 -1 -1 68 355 275 147...
result:
ok 2000 numbers
Test #13:
score: 10
Accepted
time: 47ms
memory: 66788kb
input:
2000 2000 2000 1057 1968 457 468 920 715 56 1653 1457 229 581 1751 1289 1738 268 403 1254 1996 1878 1456 1891 250 200 1729 651 1667 1870 1125 596 1287 1166 556 1783 1201 837 703 426 1523 1730 1151 1154 564 892 1273 1068 440 1481 248 241 1861 704 1556 720 1960 91 1535 75 221 1436 1561 1133 965 468 15...
output:
174 243 113 81 488 81 54 20 37 121 -1 108 39 51 -1 77 163 234 185 38 176 43 3 104 96 167 158 18 22 -1 13 -1 -1 101 -1 31 82 9 0 220 197 155 -1 83 32 48 248 144 36 200 240 241 3 -1 47 62 196 17 -1 80 176 40 -1 26 192 100 199 19 8 -1 78 -1 514 141 9 -1 5 138 -1 129 209 -1 -1 325 -1 -1 247 170 383 66 6...
result:
ok 2000 numbers
Test #14:
score: 10
Accepted
time: 51ms
memory: 72792kb
input:
2000 2000 2000 817 926 1659 1203 1736 806 1653 705 1801 1424 476 698 115 392 269 96 391 1094 419 1683 1079 1216 1080 1378 1846 492 837 871 1237 498 1307 1367 929 734 1149 1000 721 118 757 567 843 985 665 1662 1422 1418 79 1326 28 801 1 254 1821 1901 1737 747 726 292 1607 52 1321 1049 943 1543 1527 7...
output:
-1 -1 57 35 2 -1 298 -1 -1 320 408 95 45 -1 42 463 578 -1 39 423 290 -1 184 105 235 -1 -1 311 -1 663 270 0 518 7 66 471 107 307 166 633 168 190 136 -1 174 -1 330 59 324 -1 199 -1 356 61 155 510 107 702 -1 -1 -1 -1 54 174 407 75 144 461 -1 96 -1 513 66 -1 187 -1 -1 139 54 499 -1 611 -1 -1 243 504 -1 ...
result:
ok 2000 numbers
Test #15:
score: 10
Accepted
time: 68ms
memory: 90844kb
input:
2000 2000 2000 1681 700 1949 700 1904 700 700 1715 700 46 1 700 700 870 1044 700 700 586 700 766 731 700 700 720 700 313 700 1064 1459 700 189 700 700 1063 700 113 891 700 700 141 700 1073 700 510 700 989 700 683 700 1328 1513 700 1096 700 618 700 700 509 919 700 196 700 700 1672 700 1763 1733 700 9...
output:
0 2 1 0 3 4 0 -1 1 1 1 -1 2 1 -1 1 0 0 2 0 4 2 -1 -1 1 1 2 2 0 6 3 -1 -1 1 0 1 0 1 0 4 0 4 0 0 0 -1 0 -1 3 0 0 0 2 -1 0 1 -1 -1 -1 1 0 0 0 3 1 2 1 0 0 0 0 0 -1 0 0 0 3 4 0 0 -1 -1 1 -1 2 -1 0 -1 0 -1 1 0 2 -1 -1 1 0 0 1 2 0 2 -1 1 6 -1 0 1 -1 2 -1 0 4 0 -1 3 0 1 1 2 -1 0 3 0 0 1 1 -1 2 5 0 4 4 1 0 0...
result:
ok 2000 numbers
Test #16:
score: 10
Accepted
time: 56ms
memory: 78824kb
input:
2000 2000 2000 1523 891 1530 891 891 1477 1199 891 891 1499 891 326 1043 891 1629 891 891 1686 891 1334 891 795 1483 891 1618 891 1243 891 1482 891 891 606 96 891 891 1904 1750 891 401 891 891 1456 891 859 769 891 891 1663 891 70 891 161 891 559 891 217 891 571 1699 891 891 250 1655 891 1648 891 184...
output:
0 -1 -1 -1 0 6 1 3 1 -1 0 1 4 -1 0 2 1 2 0 2 6 0 1 -1 -1 -1 0 1 0 -1 0 6 5 0 -1 1 -1 0 -1 2 4 -1 -1 0 5 1 1 -1 1 3 2 0 -1 -1 2 1 2 -1 1 2 0 2 1 0 2 2 3 2 0 -1 -1 -1 -1 -1 2 0 0 0 -1 0 0 -1 -1 2 1 0 0 2 -1 3 0 -1 -1 0 0 2 -1 2 0 -1 2 2 5 -1 0 -1 0 5 0 1 0 3 -1 2 0 1 1 0 3 -1 0 -1 1 2 0 0 2 0 0 3 4 -1...
result:
ok 2000 numbers
Test #17:
score: 10
Accepted
time: 46ms
memory: 104976kb
input:
2000 2000 2000 1284 391 1284 555 1284 1509 1577 1284 763 1284 1284 332 1284 570 1284 1101 1761 1284 1759 1284 1529 1284 1284 1466 4 1284 1284 744 142 1284 1765 1284 1015 1284 1284 1189 1747 1284 1386 1284 1284 606 124 1284 1284 768 1020 1284 1284 379 1284 1914 1652 1284 129 1284 1032 1284 1284 70 12...
output:
0 1 0 -1 1 1 1 1 0 0 1 3 1 3 1 4 0 0 -1 0 3 1 1 0 0 0 1 -1 0 1 0 1 2 3 0 1 -1 0 2 1 -1 0 0 5 4 0 0 2 -1 5 5 2 0 0 3 6 3 1 0 -1 5 0 -1 3 0 0 3 2 2 3 3 0 1 -1 0 -1 0 0 0 1 -1 4 2 4 2 0 1 -1 4 0 0 0 1 0 2 1 0 0 2 4 0 1 0 0 -1 -1 1 8 3 3 1 -1 4 3 2 2 2 1 0 -1 11 0 1 0 1 -1 3 2 3 0 -1 0 -1 1 1 -1 0 1 0 -...
result:
ok 2000 numbers
Test #18:
score: 10
Accepted
time: 56ms
memory: 105348kb
input:
2000 2000 2000 1197 238 814 238 1746 238 321 238 238 797 776 238 238 109 238 285 724 238 238 149 238 1737 238 249 238 473 238 420 699 238 779 238 304 238 889 238 238 1626 238 923 238 1810 1120 238 1463 238 437 238 238 1779 238 929 238 949 238 1483 223 238 1544 238 238 981 1978 238 293 238 494 238 17...
output:
0 0 0 4 -1 0 -1 1 2 2 0 0 -1 1 3 2 1 2 1 -1 0 2 0 -1 -1 1 2 -1 3 -1 -1 1 3 2 -1 4 -1 0 1 5 -1 2 1 0 0 -1 1 2 0 4 -1 0 -1 1 3 0 -1 -1 3 -1 0 0 6 0 0 0 1 -1 0 0 0 2 0 1 -1 1 2 0 -1 3 3 4 0 0 0 5 1 0 0 3 0 2 1 2 -1 2 0 1 2 0 2 1 0 0 4 0 -1 0 -1 0 0 2 1 3 1 0 -1 1 0 0 0 3 4 6 -1 2 -1 -1 0 3 0 -1 1 -1 3 ...
result:
ok 2000 numbers
Test #19:
score: 10
Accepted
time: 44ms
memory: 104572kb
input:
2000 2000 2000 23 1970 854 76 1538 706 612 807 900 1523 258 1046 738 1821 541 931 762 1406 1205 1080 1006 211 810 1190 39 1727 397 850 572 569 1447 1745 1057 1400 1459 696 1822 1309 1703 1833 1611 683 1362 579 1426 63 261 271 1418 1587 814 309 224 1327 1166 1239 113 1581 14 895 1098 267 368 1340 163...
output:
1528 -1 3 -1 491 5 1291 929 1412 1161 2 9 -1 -1 -1 4 842 -1 578 1385 4 -1 -1 6 1629 -1 -1 9 183 4 7 0 -1 280 -1 677 -1 922 1156 775 -1 -1 11 9 1573 200 -1 1698 452 611 1 -1 737 1104 9 -1 4 542 10 -1 3 1 488 380 -1 13 5 -1 1434 798 543 589 4 -1 -1 1 6 7 -1 -1 -1 523 5 -1 1756 801 1 372 1101 1593 3 10...
result:
ok 2000 numbers
Test #20:
score: 10
Accepted
time: 47ms
memory: 103860kb
input:
2000 2000 2000 123 1636 53 1142 1587 1681 1871 481 959 634 1162 342 815 1745 663 794 122 863 1809 581 179 1822 26 1072 478 513 564 1116 1751 383 834 222 1805 5 1483 1517 1283 833 1191 209 621 780 1665 1047 205 14 1826 480 170 203 1095 1276 542 470 750 1760 539 573 1728 219 1756 1898 906 1616 884 190...
output:
0 1 3 3 0 -1 -1 1507 709 878 1 -1 -1 6 -1 5 10 10 0 16 -1 1798 -1 3 -1 7 1142 3 -1 -1 7 2 1 405 0 -1 3 1257 10 -1 54 -1 -1 3 488 6 1243 -1 -1 -1 2 964 4 988 -1 1309 1379 3 2 1810 2 2 27 188 0 -1 -1 1293 494 559 1 475 511 5 -1 6 3 -1 663 9 -1 1185 7 6 -1 232 3 -1 -1 -1 406 -1 1 -1 6 1 3 492 76 3 -1 4...
result:
ok 2000 numbers
Test #21:
score: 10
Accepted
time: 45ms
memory: 103220kb
input:
2000 2000 2000 799 1750 150 482 1299 1970 1106 1409 1392 167 324 693 584 555 1703 1440 62 1001 1681 1652 145 371 1019 1842 1041 512 1263 81 1816 435 7 1470 1301 857 1506 1742 1759 1891 1245 1968 616 913 1653 1282 1014 143 1501 1753 1248 1444 875 1668 1382 1426 132 1260 264 1707 497 1124 1073 1926 56...
output:
0 -1 -1 1 482 6 4 0 386 4 2 652 0 4 160 0 -1 -1 3 0 758 900 1 -1 488 -1 -1 -1 845 -1 221 -1 -1 -1 -1 5 1311 6 -1 3 1074 1086 -1 1 -1 1359 5 95 -1 -1 -1 5 0 540 228 1 820 7 646 -1 207 -1 1604 -1 -1 2 -1 -1 15 1 1031 -1 -1 222 6 -1 -1 2 -1 -1 0 5 -1 1339 -1 -1 -1 1162 462 5 97 68 5 0 977 4 -1 1 663 13...
result:
ok 2000 numbers
Test #22:
score: 10
Accepted
time: 62ms
memory: 105088kb
input:
2000 2000 2000 1853 1944 457 1237 1133 1761 1205 1106 605 1166 1175 97 722 909 681 359 852 1716 1935 268 1 1588 1900 1082 1868 588 1179 1345 1493 1106 482 52 276 156 1880 1905 497 858 290 640 1508 531 1753 1886 923 1865 661 569 1689 1787 962 992 858 1424 807 524 1212 1556 1608 1783 1251 1686 1337 30...
output:
5 -1 17 1 20 0 13 24 -1 10 4 6 8 -1 -1 5 12 16 6 14 -1 13 9 -1 20 15 7 -1 1 5 16 8 29 13 -1 -1 9 0 4 -1 24 -1 7 18 12 12 11 -1 17 0 16 18 8 10 -1 -1 0 0 19 2 12 -1 -1 -1 4 3 29 6 21 6 1 14 5 -1 7 18 12 10 18 -1 15 4 1 -1 13 12 -1 4 0 15 -1 4 4 -1 -1 14 24 17 17 25 9 24 25 7 -1 20 9 8 19 19 -1 4 14 1...
result:
ok 2000 numbers
Test #23:
score: 10
Accepted
time: 32ms
memory: 105224kb
input:
2000 2000 2000 1108 1148 1264 1635 127 216 1391 874 548 1746 855 1360 1887 1620 1 1707 1584 804 70 149 796 1344 366 764 677 1199 1247 1549 1265 1122 1052 777 1598 1340 691 1897 669 543 103 1182 1644 1774 1609 1588 1758 1736 745 1752 953 1067 1526 1391 397 908 1616 1360 1056 1657 1399 123 1783 1088 1...
output:
6 5 4 8 1 5 18 13 -1 5 1 1 -1 9 10 -1 8 -1 13 6 15 0 9 0 -1 1 -1 8 2 6 -1 6 15 11 14 0 6 -1 6 5 4 -1 3 -1 -1 2 -1 -1 2 6 -1 -1 3 11 2 9 6 8 -1 -1 13 14 0 6 10 -1 8 0 10 -1 -1 6 2 5 -1 3 6 11 9 -1 4 9 7 3 13 3 2 4 13 -1 3 -1 6 -1 3 10 7 -1 0 0 -1 0 5 2 9 5 7 11 4 0 6 8 3 6 15 3 -1 -1 -1 -1 -1 -1 4 2 ...
result:
ok 2000 numbers
Test #24:
score: 10
Accepted
time: 47ms
memory: 100860kb
input:
2000 2000 2000 255 874 1314 518 1597 995 1523 580 1776 886 184 1078 1756 1297 1090 1345 797 974 816 1707 190 915 89 933 1109 615 812 148 526 1133 1212 1444 1354 1171 309 583 1693 648 1934 1728 1408 945 1099 1120 306 1526 1019 854 39 848 1517 467 472 1719 1387 1446 1411 930 1527 1512 1902 108 2000 14...
output:
-1 7 -1 -1 9 9 -1 2 -1 1 9 7 -1 12 15 16 -1 11 5 14 7 -1 1 -1 7 6 1 0 3 3 12 -1 4 11 6 4 7 7 9 -1 11 24 11 5 -1 -1 13 10 -1 -1 15 15 -1 0 6 -1 7 -1 6 -1 7 0 7 -1 -1 -1 5 4 -1 6 2 0 0 -1 -1 5 7 0 4 0 16 24 14 2 -1 17 7 4 2 8 3 -1 -1 -1 7 1 -1 12 3 4 -1 10 1 2 2 3 3 -1 7 9 -1 1 -1 13 10 25 -1 2 24 1 2...
result:
ok 2000 numbers
Test #25:
score: 10
Accepted
time: 39ms
memory: 102964kb
input:
2000 2000 2000 1489 758 1279 791 1681 1107 363 1170 1181 958 1186 897 577 1482 1540 556 810 1555 1897 580 1121 127 104 78 811 1916 1559 817 1062 112 889 769 298 343 716 660 1101 1115 801 712 1037 1332 622 1276 1322 731 430 1892 1048 1880 498 1778 1180 226 478 435 770 1750 1503 1989 854 1032 321 882 ...
output:
0 0 0 0 8 0 0 21 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 31 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 9 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 6 0 0 0 0 0 0 0 0 ...
result:
ok 2000 numbers
Test #26:
score: 10
Accepted
time: 53ms
memory: 104240kb
input:
2000 2000 2000 1561 1398 424 826 141 904 547 1655 55 634 310 555 1370 22 530 1867 1694 1314 818 698 1653 1855 1925 509 1336 278 1835 1862 1938 270 611 1312 1503 812 289 1952 473 657 831 1086 781 1062 609 1692 1693 336 197 324 1306 749 170 1584 1550 958 4 592 849 596 609 206 1470 415 1251 1619 1925 4...
output:
1 0 12 2 13 -1 -1 -1 4 9 3 4 0 11 -1 7 16 11 9 -1 25 -1 1 2 2 5 7 3 12 15 -1 2 7 -1 0 1 -1 -1 -1 -1 1 17 25 5 -1 -1 6 9 6 -1 -1 -1 17 -1 9 14 2 8 8 9 15 -1 -1 5 8 -1 -1 2 0 2 2 11 3 -1 -1 6 13 -1 4 -1 1 -1 -1 2 -1 -1 23 0 -1 1 6 10 7 -1 15 0 16 -1 1 1 6 -1 6 4 15 25 7 30 0 -1 1 17 22 -1 -1 5 -1 2 8 ...
result:
ok 2000 numbers
Test #27:
score: 10
Accepted
time: 50ms
memory: 96840kb
input:
2000 2000 2000 1302 656 774 642 859 134 379 98 1620 537 1446 638 522 1333 1993 1818 1583 1629 42 1614 201 84 1211 1620 230 1431 1319 1917 1647 856 1967 1028 1872 1712 1116 1320 1322 948 1669 1943 689 871 272 656 972 113 1475 982 1579 530 1763 1418 1797 751 1864 1143 1951 782 1562 1804 510 1684 1759 ...
output:
13 13 10 -1 3 7 17 -1 23 5 3 3 0 12 8 -1 11 5 3 -1 6 7 8 2 7 8 4 1 8 5 7 18 -1 -1 11 4 4 6 12 13 -1 7 7 25 -1 11 6 11 1 4 -1 1 1 7 0 -1 -1 0 1 -1 -1 -1 14 16 4 -1 9 -1 14 3 6 16 7 21 2 -1 4 1 -1 -1 3 2 12 0 3 1 -1 8 2 -1 7 12 -1 9 13 3 8 18 4 5 -1 1 13 14 -1 14 4 0 18 10 0 9 3 11 10 12 4 3 10 6 6 24...
result:
ok 2000 numbers
Test #28:
score: 10
Accepted
time: 57ms
memory: 90808kb
input:
2000 2000 2000 221 1490 1700 403 501 1001 927 1491 165 960 1583 1136 284 446 1245 331 106 1922 995 363 1084 1011 1271 86 658 1259 681 589 756 1218 910 1716 944 1387 723 757 912 1457 773 867 1050 1825 1942 1077 186 1672 681 1401 1324 1559 374 1957 58 230 881 878 133 325 1326 1096 1475 215 549 602 185...
output:
16 0 14 0 3 3 -1 -1 11 7 -1 8 4 1 5 8 33 3 5 -1 14 15 0 8 11 13 0 0 3 -1 9 -1 0 8 13 14 -1 4 13 4 18 5 6 -1 2 8 6 1 -1 -1 16 -1 -1 0 -1 7 2 -1 14 10 3 4 15 26 5 19 3 5 -1 -1 -1 3 1 -1 13 8 5 15 -1 23 19 1 -1 -1 11 21 4 -1 -1 18 14 18 3 13 5 12 0 4 10 2 12 4 -1 13 6 8 2 3 14 8 26 -1 11 11 7 3 7 2 9 -...
result:
ok 2000 numbers
Test #29:
score: 10
Accepted
time: 51ms
memory: 94884kb
input:
2000 2000 2000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51...
output:
348 55 510 -1 248 1713 217 -1 652 -1 18 74 -1 49 137 1558 1485 901 -1 341 42 -1 -1 1081 -1 -1 -1 -1 698 87 414 128 -1 6 502 833 659 955 60 731 143 366 167 266 320 249 36 -1 203 287 345 2057 405 384 179 1138 -1 356 82 5 253 191 1254 270 401 912 452 381 665 -1 615 751 329 836 18 -1 -1 66 -1 -1 220 88 ...
result:
ok 2000 numbers
Test #30:
score: 10
Accepted
time: 49ms
memory: 104712kb
input:
2000 2000 2000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51...
output:
90 1053 59 1149 -1 -1 -1 86 406 288 8 116 174 3 -1 881 -1 167 968 -1 365 -1 -1 -1 -1 -1 96 213 -1 101 -1 0 1821 -1 -1 -1 753 -1 8 -1 2496 832 -1 -1 102 139 1567 3 563 274 -1 1039 96 -1 -1 616 518 662 -1 304 -1 -1 220 1066 162 391 592 77 493 197 642 124 -1 41 821 226 -1 52 -1 -1 63 154 1514 -1 866 -1...
result:
ok 2000 numbers
Test #31:
score: 10
Accepted
time: 44ms
memory: 104808kb
input:
2000 2000 2000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51...
output:
166 312 25 35 1400 1340 -1 608 946 120 118 184 202 353 92 -1 -1 -1 627 224 213 1545 21 219 366 -1 -1 -1 474 54 95 752 4 294 108 -1 136 -1 1457 132 -1 84 -1 17 755 -1 382 5 224 -1 139 115 378 98 165 -1 133 468 144 10 896 7 29 58 -1 -1 -1 485 -1 593 -1 5 51 942 558 1218 413 1094 -1 599 1238 315 401 96...
result:
ok 2000 numbers
Subtask #2:
score: 0
Time Limit Exceeded
Test #32:
score: 28
Accepted
time: 3158ms
memory: 124388kb
input:
99819 89735 60985 59741 24953 61387 12293 53761 1828 60970 60534 40598 48807 21876 21232 29527 13335 84269 40756 89571 12996 25757 40587 52477 63347 41372 69243 16391 58678 40854 39513 84384 91744 62938 60371 81932 45504 34121 54746 51945 14294 883 85344 78845 51797 45025 76590 37694 65493 4118 2588...
output:
36 -1 12 59 9 5 652673843 3 422622756 -1 -1 -1 29 -1 -1 -1 13 427634455 18 265926271 263974211 877045993 8 288833077 997549690 644774220 16 995218986 31 30 924036742 19 19 2 -1 10 -1 4393606 22 2 932888431 991013529 14 14 -1 6 -1 19 1 20 8 502124020 726366843 1 24 119719836 -1 25 217737158 -1 941591...
result:
ok 60985 numbers
Test #33:
score: 28
Accepted
time: 3720ms
memory: 127820kb
input:
65792 82260 98345 2807 36704 10610 16927 54219 65426 24263 25305 13397 46673 60999 3285 35985 24016 10517 9010 4968 22658 30974 31951 38242 17952 61100 8530 15143 8846 61270 11644 8471 2574 41231 48185 62800 35928 39726 5051 8526 43440 35896 29662 41894 56913 52781 49717 26456 16360 32511 37106 2284...
output:
8 5 882373032 23 1 1 -1 -1 356931161 39 341872751 7 443103688 21 477952848 -1 4 -1 753271794 262323059 532395174 11 21 16 16 24 853345123 816626114 4 772964226 431526730 -1 5 21 627951453 204273333 -1 401693620 984451652 -1 -1 18 29 -1 555626761 -1 875205996 -1 117944225 125509799 15 -1 10 238336545...
result:
ok 98345 numbers
Test #34:
score: 0
Time Limit Exceeded
input:
81509 65745 92452 49354 34810 8622 33343 50412 37468 49936 15350 28400 76011 5783 77041 61734 75149 67014 22641 4383 53957 28387 47981 31116 29067 75760 43023 23755 42103 47843 18332 62808 52998 5475 54810 28429 30311 66710 41985 27014 941 22865 26848 23077 70957 63837 44035 76582 15522 34929 56916 ...
output:
result:
Subtask #3:
score: 0
Time Limit Exceeded
Test #59:
score: 30
Accepted
time: 2598ms
memory: 128088kb
input:
95629 64841 64314 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51...
output:
-1 701714740 -1 610354140 816755067 2440 245932872 -1 29509 866966613 744072492 890 -1 969398264 588051152 381506396 2347 5427 4829 44377 195466300 60823 508 459304253 400544113 -1 787773518 3856 9692 6576 322820913 900985028 1473 14691 26175 -1 27082 -1 9735 3846 537036842 -1 261459575 86658 635912...
result:
ok 64314 numbers
Test #60:
score: 30
Accepted
time: 2582ms
memory: 130008kb
input:
92502 51399 68929 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51...
output:
36266 -1 -1 112572200 27068354 -1 10394 329233107 444229297 223185833 363055390 1754 14433 -1 4346 -1 33082 457460095 -1 5482 749013593 717085104 5006 -1 926464006 1983 589805099 7590 264497528 8979 903766762 24704 903 923960764 4211 53272133 17012 435443676 -1 984123705 -1 1980 -1 2907 20373 813690...
result:
ok 68929 numbers
Test #61:
score: 30
Accepted
time: 2973ms
memory: 130356kb
input:
53810 92751 89379 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51...
output:
462043454 6397 31647 98446547 81496 14 34784 1587 532169187 35742 753712897 400460299 299860851 -1 26049 984595650 8185 13794 721579357 166901630 16093 -1 48327 52280 -1 36956 49549 33065 703982006 15511 171757272 130683368 -1 16949 -1 96442497 948433381 -1 -1 -1 3 55603 -1 120939988 12974 952750599...
result:
ok 89379 numbers
Test #62:
score: 0
Time Limit Exceeded
input:
100000 100000 100000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50...
output:
22357 29573 45104 2184 -1 109258 31337 -1 26387 41578 8392 36172 1160 9470 -1 6923 -1 -1 302 26401 -1 52971 25666 1970 104774 -1 33764 -1 -1 43624 5470 26387 38352 -1 8495 8983 7396 8448 4711 72385 -1 4832 -1 5388 4583 1151 38790 30979 -1 17732 28535 45088 -1 -1 97310 15663 92961 12755 949 -1 22729 ...
result:
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%