QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#504904 | #7610. Bus Lines | pandapythoner | AC ✓ | 2008ms | 75616kb | C++23 | 5.5kb | 2024-08-04 17:09:47 | 2024-08-04 17:09:49 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define rep(i, n) for(int i = 0; i < n; i += 1)
#define len(a) ((int)(a).size())
const ll inf = 1e18;
mt19937 rnd(234);
const int logn = 18;
const int maxn = 2e5 + 1000;
const int maxm = 2e5 + 1000;
int n, m;
vector<vector<int>> g;
pair<int, int> busses[maxm];
int bup[maxn][logn];
int sz[maxn];
int c;
int tin[maxn], tout[maxn];
int h[maxn];
int par[maxn];
int up[maxn], up_deg[maxn];
ll dp_down[maxn], dp_up[maxn];
vector<int> busses_graph[maxn];
struct tin_comp {
bool operator()(int u, int v) const { return tin[u] < tin[v]; }
};
ll sum = 0;
ll great_val[maxn];
ll great_val_sum[maxn];
int total_lca = -1;
set<int, tin_comp> st;
ll result[maxn];
int lca(int u, int v);
void clear() {
st.clear();
total_lca = -1;
sum = 0;
}
void add_vertex(int v) {
if (st.count(v)) return;
if (total_lca == -1) total_lca = v;
else total_lca = lca(total_lca, v);
auto it = st.insert(v).first;
sum += great_val_sum[v];
int a = -1;
int b = -1;
if (it != st.begin()) {
a = *prev(it);
int t = lca(a, v);
sum -= great_val_sum[t];
}
if (next(it) != st.end()) {
b = *next(it);
int t = lca(b, v);
sum -= great_val_sum[t];
}
if (a != -1 and b != -1) {
sum += great_val_sum[lca(a, b)];
}
}
ll get_sum() {
ll result = sum;
if (total_lca != -1 and total_lca != 0) {
result -= great_val_sum[par[total_lca]];
result += dp_down[total_lca];
}
return result;
}
void dfs1(int v, int p) {
par[v] = bup[v][0] = p;
for (int i = 1; i < logn; i += 1) {
bup[v][i] = bup[bup[v][i - 1]][i - 1];
}
rep(i, len(g[v])) if (g[v][i] == p) {
g[v].erase(g[v].begin() + i);
break;
}
sz[v] = 1;
int mxsz = -1;
int mxszi = -1;
rep(i, len(g[v])) {
int to = g[v][i];
dfs1(to, v);
sz[v] += sz[to];
if (mxsz < sz[to]) {
mxsz = sz[to];
mxszi = i;
}
}
if (mxszi != -1) {
swap(g[v][0], g[v][mxszi]);
}
}
void dfs2(int v, int mh = 0) {
tin[v] = c++;
h[v] = mh;
for (auto to : g[v]) {
dfs2(to, mh + 1);
}
tout[v] = c;
}
int go_up(int v, int x) {
rep(i, logn) {
if ((x >> i) & 1) {
v = bup[v][i];
}
}
return v;
}
int lca(int u, int v) {
if (h[u] < h[v]) swap(u, v);
u = go_up(u, h[u] - h[v]);
if (u == v) return u;
for (int i = logn - 1; i >= 0; i -= 1) {
if (bup[u][i] != bup[v][i]) {
u = bup[u][i];
v = bup[v][i];
}
}
assert(u != v);
return par[u];
}
void dfs3(int v) {
for (auto to : g[v]) {
dfs3(to);
if (h[up[v]] > h[up[to]]) {
up[v] = up[to];
}
}
assert(v == 0 or h[up[v]] < h[v]);
up_deg[v] += 1;
up_deg[up[v]] += up_deg[v];
dp_down[v] = up_deg[v];
for (auto to : g[v]) {
dp_down[v] += dp_down[to];
}
}
void dfs4(int v, ll sum = 0) {
sum += great_val[v];
great_val_sum[v] = sum;
for (auto to : g[v]) {
dfs4(to, sum);
}
}
void dfs6(int);
void dfs5(int v) {
for (int i = len(g[v]) - 1; i >= 0; i -= 1) {
clear();
int to = g[v][i];
dfs5(to);
}
for (int i = 1; i < len(g[v]); i += 1) {
int to = g[v][i];
dfs6(to);
}
for (auto u : busses_graph[v]) {
add_vertex(u);
}
if (g[v].empty()) add_vertex(v);
dp_up[v] = n - sz[v] + get_sum();
}
void dfs6(int v) {
for (auto u : busses_graph[v]) {
add_vertex(u);
}
if (g[v].empty()) add_vertex(v);
for (auto to : g[v]) dfs6(to);
}
void dfs7(int v) {
if (v != 0 and up[v] != 0) {
dp_up[v] += dp_up[up[v]];
}
for (auto to : g[v]) dfs7(to);
}
void solve() {
dfs1(0, 0);
c = 0;
dfs2(0);
rep(v, n) up[v] = v;
rep(v, n) up_deg[v] = 0;
rep(i, m) {
auto [u, v] = busses[i];
int t = lca(u, v);
if (h[up[u]] > h[t]) {
up[u] = t;
}
if (h[up[v]] > h[t]) {
up[v] = t;
}
}
dfs3(0);
dp_down[0] = 0;
rep(v, n) {
great_val[v] = -dp_down[v];
for (auto to : g[v]) great_val[v] += dp_down[to];
}
dfs4(0);
rep(i, n) dp_up[i] = 0;
rep(i, n) busses_graph[i] = {};
rep(i, m) {
auto [u, v] = busses[i];
busses_graph[u].push_back(v);
busses_graph[v].push_back(u);
}
clear();
dfs5(0);
dp_up[0] = 0;
dfs7(0);
rep(v, n) {
result[v] = dp_up[v];
for (auto to : g[v]) {
result[v] += dp_down[to];
}
}
}
int32_t main() {
if (1) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
cin >> n;
g.assign(n, vector<int>());
rep(i, n - 1) {
int u, v; cin >> u >> v; --u; --v;
g[u].push_back(v);
g[v].push_back(u);
}
cin >> m;
rep(i, m) {
int u, v; cin >> u >> v; --u; --v;
busses[i] = make_pair(u, v);
}
solve();
rep(v, n) cout << result[v] << " ";
cout << "\n";
return 0;
}
/*
6
1 2
5 4
6 5
3 1
1 5
3
6 1
2 3
6 4
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 18180kb
input:
6 1 2 5 4 6 5 3 1 1 5 3 6 1 2 3 6 4
output:
6 9 9 10 7 7
result:
ok single line: '6 9 9 10 7 7 '
Test #2:
score: 0
Accepted
time: 0ms
memory: 19884kb
input:
2 1 2 1 1 2
output:
1 1
result:
ok single line: '1 1 '
Test #3:
score: 0
Accepted
time: 75ms
memory: 24180kb
input:
16384 9137 490 3442 7239 1621 6904 13769 10250 14672 12572 14906 9437 6163 12339 15244 12016 3022 8670 3211 9106 11966 14817 15798 15876 6423 7394 894 7695 13877 1983 16342 15158 13574 15932 15125 10722 6989 15683 10335 8801 12301 4246 6166 3893 9347 12073 7897 12195 6510 3101 4526 15385 7017 7001 4...
output:
34355 34048 34070 34152 33992 33977 34077 42219 34103 33976 34065 34170 34072 34061 34069 34177 34068 34129 33872 50478 34059 33921 34153 34049 34034 33820 34132 34116 34361 33728 50043 34138 33855 33873 34309 34319 34068 50753 34135 34256 34159 34034 34056 34361 34171 34316 34058 34125 34019 34182 ...
result:
ok single line: '34355 34048 34070 34152 33992 ... 34333 33814 33294 34266 34337 '
Test #4:
score: 0
Accepted
time: 373ms
memory: 34044kb
input:
65536 44501 44259 59772 51161 51582 2027 2699 8610 5021 57211 60597 10270 29222 11423 38503 3833 52021 47503 47160 15296 61201 13465 20807 17239 7705 20234 32708 25663 7800 42265 29410 44963 32173 38920 49438 61282 25922 4342 40171 9819 12256 3995 41600 39383 57051 60932 44275 8351 8356 8295 3557 64...
output:
140178 136111 137025 136494 136304 137262 136598 135563 136530 135406 199677 137437 140282 136109 140127 136827 137235 136000 140738 139961 140081 142677 136544 201610 136181 136393 137013 137354 136855 135440 127050 136828 136781 137439 136518 185910 137170 136902 140686 136703 136847 137483 136337...
result:
ok single line: '140178 136111 137025 136494 13...63 136343 136858 137469 137325 '
Test #5:
score: 0
Accepted
time: 1166ms
memory: 51848kb
input:
131071 28270 44685 69228 113487 10873 80967 30958 109340 53006 103488 49569 111875 65021 32861 83043 36671 73613 119374 22104 91373 31527 27737 19718 27803 90762 87148 4096 41649 79425 111516 111950 123500 94580 61416 30879 18640 71251 76344 61698 28557 104875 59268 130832 61334 110927 109064 114115...
output:
273557 262588 264936 265663 265875 266353 265834 265712 376149 272370 267699 267626 267023 265515 266009 265333 278296 265843 265760 268149 267395 265340 271825 358266 268835 264845 266112 265586 265886 266374 265323 265391 266080 265499 278600 267120 265190 266164 266010 265240 265690 265370 264312...
result:
ok single line: '273557 262588 264936 265663 26...42 266079 265822 265939 266211 '
Test #6:
score: 0
Accepted
time: 361ms
memory: 57980kb
input:
131071 4458 33223 28971 26710 73930 35887 19953 56582 19448 128895 117093 55994 68752 16511 37373 128666 1236 73891 64724 74049 67901 130974 130547 112357 99689 77958 76785 17021 37348 91813 67628 67488 96598 83555 17348 74226 98935 43076 75325 83600 59427 80746 74874 122816 71615 76503 112584 12953...
output:
131070 131070 131070 131070 131070 131070 131071 131071 131071 131071 131070 131071 131070 131070 131071 131071 131070 131071 131071 131070 131070 131070 131070 131070 131071 131070 131070 131070 131070 131070 131070 131071 131070 131071 131070 131070 131070 131070 131070 131071 131070 131070 131071...
result:
ok single line: '131070 131070 131070 131070 13...70 131071 131070 131070 131071 '
Test #7:
score: 0
Accepted
time: 1206ms
memory: 50332kb
input:
131072 20415 30901 24973 116658 50309 77228 14138 108175 122283 105254 80524 41943 16756 109108 113505 71325 9649 106367 125747 68730 27704 18831 12993 123364 57489 129424 96113 82877 44188 4472 5704 86388 73653 70774 41742 33080 6701 59595 80297 22453 59925 75977 88478 91057 97666 26155 30080 55382...
output:
267346 265658 267019 267148 266495 270630 265327 266124 266100 265926 265909 266766 265785 266284 265064 266584 266146 266937 271485 265805 265480 266087 267189 264771 266288 266965 270451 265977 265706 265268 265845 267259 265723 266249 266047 266159 270563 266086 265976 265845 265431 265535 265930...
result:
ok single line: '267346 265658 267019 267148 26...80 270694 266015 266101 265704 '
Test #8:
score: 0
Accepted
time: 353ms
memory: 59768kb
input:
131072 48550 41416 47329 96006 106074 122239 948 75631 112525 117270 3358 7210 30446 101867 16965 11336 78371 58088 21081 102637 76025 92177 102359 2073 11618 50130 79150 120277 30847 51845 72881 58212 125170 71210 1909 8660 120236 81594 127702 49237 32584 53272 5049 20955 31844 125464 119524 100808...
output:
131071 131072 131078 131071 131071 131072 131072 131072 131074 131071 131071 131071 131072 131071 131071 131072 131072 131072 131071 131115 131078 131072 131074 131071 131072 131074 131071 131071 131072 131072 131074 131074 131072 131072 131074 131072 131078 131072 131077 131074 131071 131072 131072...
result:
ok single line: '131071 131072 131078 131071 13...71 131074 131072 131072 131072 '
Test #9:
score: 0
Accepted
time: 1148ms
memory: 50260kb
input:
131073 113890 124822 124669 105393 128510 64051 106729 33462 46677 33217 73570 96913 47532 130531 8593 45487 31793 58221 49510 82943 60351 62272 42636 37378 105049 94689 124230 45945 13194 123517 107928 62129 7572 15657 84304 122943 19818 59980 104221 18821 66457 91449 5072 101241 61822 5975 74471 6...
output:
266326 266281 266163 265817 265563 266929 265938 266796 265751 265513 266249 269598 266832 267310 265225 266439 266351 265499 397338 269917 266647 266193 266663 266655 269976 266497 326968 266761 266261 266672 265613 266103 265821 265496 265891 266411 265820 266598 266583 266154 265794 265587 266472...
result:
ok single line: '266326 266281 266163 265817 26...69 266180 266343 268563 266527 '
Test #10:
score: 0
Accepted
time: 396ms
memory: 56336kb
input:
131073 30694 94981 78010 61921 83010 76565 7176 94673 24081 63906 107002 35122 72499 90887 98339 109807 48362 125168 5335 63101 127350 85675 13421 77562 2375 93853 10090 23323 91852 109502 21899 90367 56580 125803 108402 88380 30465 25789 73326 29902 60781 28952 113429 111420 15039 5166 48046 85049 ...
output:
131072 131072 131073 131072 131072 131072 131072 131072 131072 131072 131072 131205 131072 131072 131072 131083 131073 131072 131083 131073 131072 131072 131072 131072 131073 131073 131072 131072 131072 131072 131072 131072 131072 131072 131072 131083 131073 131073 131072 131194 131205 131072 131072...
result:
ok single line: '131072 131072 131073 131072 13...72 131072 131072 131072 131072 '
Test #11:
score: 0
Accepted
time: 543ms
memory: 72148kb
input:
200000 303 187602 17443 90857 141584 9689 98281 37564 34044 95754 47052 855 176062 121958 162738 96296 89316 164507 150496 42874 12673 1114 24877 131213 196802 28543 78558 84878 102156 146853 143846 158517 167159 69770 16743 9610 169056 115672 127506 149401 4110 24877 150803 72957 71484 24773 50738 ...
output:
200000 200000 200001 200009 200000 200000 200000 200004 200000 200001 200009 200040 200000 200000 200371 200001 200001 200000 200005 200000 200103 200000 200005 200001 200002 200000 200004 200000 200004 200002 200001 200004 200000 200004 200103 200000 200001 200001 200009 200004 200000 200000 200009...
result:
ok single line: '200000 200000 200001 200009 20...00 200000 200000 200001 200001 '
Test #12:
score: 0
Accepted
time: 542ms
memory: 72024kb
input:
200000 91261 108952 134236 7809 30750 140934 69514 100626 174539 64746 143756 139270 75999 163614 73309 112948 110641 128653 77295 196144 112549 15212 29529 58568 34742 48981 160465 37279 60772 47631 116260 164168 140007 138837 152400 41600 46137 103771 122809 991 98335 53547 71446 60454 182926 9505...
output:
259717 224832 623118 233065 221904 225116 248347 347328 229609 227413 369557 318840 231176 228808 255754 223173 224794 339975 239690 230310 252630 225403 411260 227236 240962 241886 231002 333731 242413 226478 294844 238042 224724 260233 244253 330794 247474 231750 283982 269581 221874 223906 258662...
result:
ok single line: '259717 224832 623118 233065 22...21 228869 224599 227932 221883 '
Test #13:
score: 0
Accepted
time: 0ms
memory: 17904kb
input:
3 3 2 1 3 1 1 2
output:
2 2 2
result:
ok single line: '2 2 2 '
Test #14:
score: 0
Accepted
time: 735ms
memory: 66352kb
input:
200000 139347 147721 117297 105382 77192 197023 48135 123968 192172 102714 134778 129103 89903 62952 133541 38908 157094 5072 98697 154745 126329 161358 10578 175752 174214 105555 128475 68598 37906 187226 161543 11243 153891 97890 8751 74708 1967 76185 67263 189209 68782 199622 163887 141633 176004...
output:
322099 242574 317560 692202 290760 228294 365767 338369 353452 316822 250525 392353 334147 230213 228522 235083 402948 230055 390730 404058 356419 260604 408966 344671 228306 285866 230909 242013 251050 312234 247399 300014 275307 396635 301629 245071 324672 317767 338521 318599 251342 394339 233005...
result:
ok single line: '322099 242574 317560 692202 29...72 316661 233236 238848 229144 '
Test #15:
score: 0
Accepted
time: 779ms
memory: 65644kb
input:
200000 48091 145114 125125 28630 12239 122518 46999 28599 9536 79090 173383 59215 130797 80267 19356 192091 70170 63308 51543 84599 75128 23622 67565 61168 59080 1306 169051 40849 189030 31373 186212 42004 87480 32135 81468 163743 112945 69079 83894 23714 71122 15016 66755 85285 115054 110310 3811 4...
output:
352484 361697 353433 343102 240568 351386 298596 364831 245058 343138 260208 258681 345310 370366 432737 233034 361503 405572 231637 345073 347968 358736 232149 353892 398610 251240 431731 345221 343820 346239 347060 263522 231954 393526 360199 379830 373877 236327 353553 603138 426721 241772 231332...
result:
ok single line: '352484 361697 353433 343102 24...94 353707 382734 557096 397978 '
Test #16:
score: 0
Accepted
time: 873ms
memory: 64380kb
input:
200000 100856 98512 7263 55794 118589 8600 181408 78844 136926 96808 184915 65090 34153 123222 81629 114888 41173 81343 115395 158775 74974 23534 3836 68657 105617 97663 76598 41608 28787 13900 100912 96168 68712 136985 80113 56372 112283 126282 119777 137629 165008 120438 53426 26030 78094 83600 18...
output:
385605 380500 397966 236324 577262 360773 233242 371405 362611 369437 365600 386222 381693 250148 585672 376752 366566 253349 377273 388253 269521 263111 427010 369947 392348 389317 423904 233334 252314 359670 387478 359580 233140 434587 321068 233635 234253 365444 235007 599141 373618 362626 360872...
result:
ok single line: '385605 380500 397966 236324 57...45 241541 407294 372787 439030 '
Test #17:
score: 0
Accepted
time: 975ms
memory: 62992kb
input:
200000 180714 64749 50294 63588 118425 45210 19449 119242 106397 111631 165556 58767 54399 99326 53093 31192 63207 75350 36668 124604 80509 124402 69687 129300 190278 28893 50196 134511 46249 169905 58139 53110 87694 22713 75518 99566 179781 17413 110365 34464 27454 193678 130171 47991 174341 58040 ...
output:
409591 396787 395821 239526 599035 470672 428144 397055 392027 394551 439143 394596 388894 404545 405346 348418 392047 593706 389817 326075 394143 396508 393233 425007 399946 397646 399058 595850 413576 389700 412903 417007 392550 401326 462627 392588 275297 400751 395385 395593 398254 244287 415091...
result:
ok single line: '409591 396787 395821 239526 59...05 410665 400756 392347 468683 '
Test #18:
score: 0
Accepted
time: 1094ms
memory: 62644kb
input:
200000 30933 92193 77862 62042 158213 175855 16780 145844 1108 114460 160478 9352 82719 112145 142088 62191 15793 183238 129644 169759 70407 173026 113244 57481 56239 24998 45541 79142 119610 110586 99594 22588 198974 169804 99392 125472 63750 161647 119893 161584 25389 132271 48396 138568 63641 385...
output:
603675 406633 422392 407572 409097 406433 406205 407058 420803 408723 464911 425536 410465 481876 407605 576569 607865 431005 412229 419713 410499 412896 408749 606713 403730 427776 408406 407828 606627 417814 407449 407308 404474 470975 410304 412734 413266 406163 408984 403576 406249 405420 406787...
result:
ok single line: '603675 406633 422392 407572 40...37 412018 406965 408388 609396 '
Test #19:
score: 0
Accepted
time: 1302ms
memory: 62480kb
input:
200000 53058 81131 171867 48542 51107 57582 48378 14960 8723 5010 161623 59486 63739 114343 146033 97144 38395 143404 106830 120862 166654 142711 17747 75675 115326 57950 141271 125647 172839 194710 87377 142587 179489 111106 83353 29003 25273 100804 126366 129214 377 22864 136214 154742 26790 69245...
output:
410194 414485 812212 409671 417799 607529 444323 439505 398218 413075 406897 417525 409744 418032 416266 417491 409650 420260 411460 411034 412949 416088 409367 613828 410798 608605 411940 403730 303206 404280 403397 612430 415487 395351 408532 419160 418430 410453 416946 618525 408493 411347 423058...
result:
ok single line: '410194 414485 812212 409671 41...85 413258 416216 407728 410996 '
Test #20:
score: 0
Accepted
time: 1432ms
memory: 62268kb
input:
200000 59158 51892 164326 130454 199875 147324 154595 198150 175219 8364 108094 125630 131696 93091 63992 91024 129143 10985 79964 129833 193970 137750 130697 130080 103615 11370 83315 137120 141683 168619 130441 168268 163828 3410 76009 110247 59575 155246 124663 70547 152379 94187 114650 89902 282...
output:
418785 413603 418648 419139 412502 406320 410977 412124 407379 402640 419358 416320 407945 412692 414142 413490 413278 416746 410595 418751 415083 413390 420604 412779 418777 613129 408587 406350 413893 413360 413188 418726 401511 408363 419082 414357 526212 413422 601652 413018 411076 418011 413908...
result:
ok single line: '418785 413603 418648 419139 41...13 414570 417977 436541 415929 '
Test #21:
score: 0
Accepted
time: 286ms
memory: 75616kb
input:
200000 118922 134567 199816 52066 84326 118291 140839 91527 41156 196216 193057 168156 5712 147301 151841 143708 95806 153816 135331 166094 167087 140971 112587 136986 97546 33542 171749 67249 173810 197325 61841 77212 116769 138505 62675 30261 101896 50402 91780 178503 28880 20528 87860 154449 8267...
output:
13168057510 11173781860 10146494712 16156520832 13448332006 10989071050 10508931040 10037228302 12324541582 10347691962 10028724240 12081412506 11563767480 10187676300 12443176612 10048783240 11774557750 16609608700 15055565506 14134682902 10028318362 11956514056 10158873420 15322067256 11664028056 ...
result:
ok single line: '13168057510 11173781860 101464...110756 18856409772 13401863950 '
Test #22:
score: 0
Accepted
time: 292ms
memory: 71252kb
input:
200000 74212 14285 54279 26014 34653 159417 195912 97270 147173 32677 7753 76853 47200 73990 93075 63990 186243 107173 105569 133096 11068 124684 66637 118271 143298 65684 108858 167243 83551 3112 227 38450 120359 109554 42942 133316 29887 192012 143614 97487 95789 105585 33495 155927 63945 45781 13...
output:
9636839798 7803026188 5944133824 5022351612 5824014810 5466796520 5799132740 5020579868 5118628970 5167194124 5461475062 5089909366 9928608548 5018143302 8863291306 5172571016 6712586160 5054073146 6479682294 5284856118 6274156336 8690429520 8083401824 5218118942 5428913248 9540526484 5044191702 640...
result:
ok single line: '9636839798 7803026188 59441338...48485482 5237756436 7380188354 '
Test #23:
score: 0
Accepted
time: 349ms
memory: 65692kb
input:
200000 92107 93965 159733 109184 192340 76154 84291 151200 22927 32573 60309 166432 136353 52220 46466 195262 169506 58576 155186 181682 129591 45964 5016 99216 173166 72054 186200 95903 105499 17449 196067 122431 177329 57447 66939 50332 67438 62704 184758 103097 13997 9543 159320 119688 67521 1795...
output:
2647717540 2669067610 2536317714 4564900018 4938957828 2523583466 2587289770 4089042968 2538144128 3083739956 2846104828 4939992978 3010058766 2640028282 3303357298 3059661060 3682213356 2518446598 4593066520 3175275992 3500605592 2512952006 2728454602 4496768570 3328605822 3999565194 3852256448 268...
result:
ok single line: '2647717540 2669067610 25363177...80561904 3193035228 3613793802 '
Test #24:
score: 0
Accepted
time: 0ms
memory: 17888kb
input:
3 2 1 2 3 2 1 2 2 3
output:
3 2 3
result:
ok single line: '3 2 3 '
Test #25:
score: 0
Accepted
time: 490ms
memory: 63844kb
input:
200000 97274 52191 170698 12492 56055 38209 195479 171683 182171 104124 48099 163495 28208 143687 98769 194755 69808 115617 120295 101563 38553 94131 23270 112248 131587 158997 31823 162234 83013 181537 191160 172757 189345 102179 151357 192653 101899 101918 118524 182209 14724 52904 14881 114877 65...
output:
315521802 582270214 374296028 430835082 461750522 547580860 458554994 341017246 385629432 318527132 308318016 304520182 306364072 333253596 574032542 314446098 521022698 407699078 460444652 298495576 297416182 437728058 483072350 552191872 358261158 439148560 390171338 424559912 452883186 322464158 ...
result:
ok single line: '315521802 582270214 374296028 ... 501733906 435471700 498539190 '
Test #26:
score: 0
Accepted
time: 577ms
memory: 63852kb
input:
200000 149275 37122 186803 180793 142343 25474 2212 104891 153840 36431 70840 95284 71111 176237 88737 94284 132867 69692 115881 67641 31109 97047 21627 157384 46886 161629 143575 184545 168978 54964 39205 42574 168223 32975 102385 50620 84750 126621 109786 165166 80248 112638 7161 54171 108145 1160...
output:
156800727 185140211 160861639 163079193 181736213 166433065 169894763 127848699 165191659 128374161 137184613 136296451 122378297 150527067 186298237 142165489 171740743 163923655 144726201 186139667 216535769 143134125 206500761 150034699 166563761 130542877 215959573 147380353 174762851 188816095 ...
result:
ok single line: '156800727 185140211 160861639 ... 198578685 168950583 138834499 '
Test #27:
score: 0
Accepted
time: 891ms
memory: 51256kb
input:
131071 2 1 3 1 4 2 5 2 6 3 7 3 8 4 9 4 10 5 11 5 12 6 13 6 14 7 15 7 16 8 17 8 18 9 19 9 20 10 21 10 22 11 23 11 24 12 25 12 26 13 27 13 28 14 29 14 30 15 31 15 32 16 33 16 34 17 35 17 36 18 37 18 38 19 39 19 40 20 41 20 42 21 43 21 44 22 45 22 46 23 47 23 48 24 49 24 50 25 51 25 52 26 53 26 54 27 5...
output:
131070 131070 131070 182280 182358 182396 182254 212773 212880 212959 212834 212906 212874 212780 212908 231778 231899 231958 231796 231820 231879 231765 231895 231892 231897 231788 231917 231935 231630 231878 231824 243684 243863 243938 243663 243836 243843 243815 243694 243798 243698 243831 243802...
result:
ok single line: '131070 131070 131070 182280 18...10 262108 262110 262109 262109 '
Test #28:
score: 0
Accepted
time: 2008ms
memory: 63560kb
input:
200000 2 1 3 1 4 2 5 2 6 3 7 3 8 4 9 4 10 5 11 5 12 6 13 6 14 7 15 7 16 8 17 8 18 9 19 9 20 10 21 10 22 11 23 11 24 12 25 12 26 13 27 13 28 14 29 14 30 15 31 15 32 16 33 16 34 17 35 17 36 18 37 18 38 19 39 19 40 20 41 20 42 21 43 21 44 22 45 22 46 23 47 23 48 24 49 24 50 25 51 25 52 26 53 26 54 27 5...
output:
199999 199999 199999 270262 270338 256650 263828 314788 314651 314909 314789 296669 306837 306858 307041 344034 344207 343935 344033 344234 344132 343944 344267 323943 338165 338282 338012 338010 338278 338024 338183 363927 363728 363701 364016 363891 363723 363903 363943 364207 363770 364084 363899...
result:
ok single line: '199999 199999 199999 270262 27...38 399935 399952 399941 399950 '
Test #29:
score: 0
Accepted
time: 2007ms
memory: 63396kb
input:
200000 2 1 3 1 4 2 5 2 6 3 7 3 8 4 9 4 10 5 11 5 12 6 13 6 14 7 15 7 16 8 17 8 18 9 19 9 20 10 21 10 22 11 23 11 24 12 25 12 26 13 27 13 28 14 29 14 30 15 31 15 32 16 33 16 34 17 35 17 36 18 37 18 38 19 39 19 40 20 41 20 42 21 43 21 44 22 45 22 46 23 47 23 48 24 49 24 50 25 51 25 52 26 53 26 54 27 5...
output:
199999 199999 199999 270280 270281 256568 264051 314791 314703 314807 314898 296686 306740 307060 307152 343985 344188 343968 343978 344132 343950 344140 344015 323926 338128 337970 338070 338265 338213 338358 338125 363833 363803 363874 363896 363900 363746 363692 363889 363786 363925 363911 363775...
result:
ok single line: '199999 199999 199999 270280 27...39 399953 399937 399939 399937 '
Test #30:
score: 0
Accepted
time: 537ms
memory: 43396kb
input:
131071 2 1 3 1 4 2 5 2 6 3 7 3 8 4 9 4 10 5 11 5 12 6 13 6 14 7 15 7 16 8 17 8 18 9 19 9 20 10 21 10 22 11 23 11 24 12 25 12 26 13 27 13 28 14 29 14 30 15 31 15 32 16 33 16 34 17 35 17 36 18 37 18 38 19 39 19 40 20 41 20 42 21 43 21 44 22 45 22 46 23 47 23 48 24 49 24 50 25 51 25 52 26 53 26 54 27 5...
output:
131070 131070 131070 184799 184843 184800 184829 217005 217033 217100 216971 216982 216966 216950 217126 236023 236111 236122 236094 236140 236171 236092 236061 236028 236043 236068 236008 236123 236095 236158 236268 247294 247277 247287 247231 247276 247264 247224 247281 247294 247216 247256 247270...
result:
ok single line: '131070 131070 131070 184799 18...08 262108 262108 262108 262108 '
Test #31:
score: 0
Accepted
time: 1734ms
memory: 55612kb
input:
200000 2 1 3 1 4 2 5 2 6 3 7 3 8 4 9 4 10 5 11 5 12 6 13 6 14 7 15 7 16 8 17 8 18 9 19 9 20 10 21 10 22 11 23 11 24 12 25 12 26 13 27 13 28 14 29 14 30 15 31 15 32 16 33 16 34 17 35 17 36 18 37 18 38 19 39 19 40 20 41 20 42 21 43 21 44 22 45 22 46 23 47 23 48 24 49 24 50 25 51 25 52 26 53 26 54 27 5...
output:
199999 199999 199999 266202 266155 240079 246034 305437 305423 305403 305492 277024 288045 288193 288165 334579 334476 334657 334517 334515 334737 334772 334673 307254 324135 324262 324310 323971 324233 324346 324298 357001 356766 356841 356766 357114 356952 356916 356789 356939 356889 356833 356904...
result:
ok single line: '199999 199999 199999 266202 26...16 399899 399907 399904 399893 '
Test #32:
score: 0
Accepted
time: 1709ms
memory: 55748kb
input:
200000 2 1 3 1 4 2 5 2 6 3 7 3 8 4 9 4 10 5 11 5 12 6 13 6 14 7 15 7 16 8 17 8 18 9 19 9 20 10 21 10 22 11 23 11 24 12 25 12 26 13 27 13 28 14 29 14 30 15 31 15 32 16 33 16 34 17 35 17 36 18 37 18 38 19 39 19 40 20 41 20 42 21 43 21 44 22 45 22 46 23 47 23 48 24 49 24 50 25 51 25 52 26 53 26 54 27 5...
output:
199999 199999 199999 266198 266176 240035 245995 305476 305528 305426 305350 276894 288169 288156 287994 334767 334568 334626 334738 334701 334412 334616 334539 307261 324335 324446 324383 324266 324369 324449 324205 356954 356892 356897 356815 356935 356814 356889 356968 356924 356904 356664 356857...
result:
ok single line: '199999 199999 199999 266198 26...92 399892 399906 399896 399893 '
Test #33:
score: 0
Accepted
time: 1461ms
memory: 64648kb
input:
199989 2 1 3 1 4 2 5 3 6 4 7 5 8 6 9 7 10 8 11 9 12 10 13 11 14 12 15 13 16 14 17 15 18 16 19 17 20 18 21 19 22 20 23 21 24 22 25 23 26 24 27 25 28 26 29 27 30 28 31 29 32 30 33 31 34 32 35 33 36 34 37 35 38 36 39 37 40 38 41 39 42 40 43 41 44 42 45 43 46 44 47 45 48 46 49 47 50 48 51 49 52 50 53 51...
output:
199988 199989 199989 199990 199990 199991 199991 199992 199992 199993 199993 199994 199994 199995 199995 199996 199996 199997 199997 199998 199998 199999 199999 200000 200000 200001 200001 200002 200002 200003 200003 200004 200004 200005 200005 200006 200006 200007 200007 200008 200008 200009 200009...
result:
ok single line: '199988 199989 199989 199990 19...30 389951 389957 389943 389968 '
Test #34:
score: 0
Accepted
time: 466ms
memory: 66064kb
input:
199985 2 1 3 1 4 2 5 3 6 4 7 5 8 6 9 7 10 8 11 9 12 10 13 11 14 12 15 13 16 14 17 15 18 16 19 17 20 18 21 19 22 20 23 21 24 22 25 23 26 24 27 25 28 26 29 27 30 28 31 29 32 30 33 31 34 32 35 33 36 34 37 35 38 36 39 37 40 38 41 39 42 40 43 41 44 42 45 43 46 44 47 45 48 46 49 47 50 48 51 49 52 50 53 51...
output:
199984 199985 199985 199986 199986 199987 199987 199988 199988 199989 199989 199990 199990 199991 199991 199992 199992 199993 199993 199994 199994 199995 199995 199996 199996 199997 199997 199998 199998 199999 199999 200000 200000 200001 200001 200002 200002 200003 200003 200004 200004 200005 200005...
result:
ok single line: '199984 199985 199985 199986 19...64 374965 374967 374967 374967 '
Test #35:
score: 0
Accepted
time: 0ms
memory: 19932kb
input:
4 2 1 4 3 1 3 4 3 2 3 4 2 1 2 1
output:
4 4 3 5
result:
ok single line: '4 4 3 5 '
Test #36:
score: 0
Accepted
time: 1677ms
memory: 64592kb
input:
199989 2 1 3 1 4 2 5 3 6 4 7 5 8 6 9 7 10 8 11 9 12 10 13 11 14 12 15 13 16 14 17 15 18 16 19 17 20 18 21 19 22 20 23 21 24 22 25 23 26 24 27 25 28 26 29 27 30 28 31 29 32 30 33 31 34 32 35 33 36 34 37 35 38 36 39 37 40 38 41 39 42 40 43 41 44 42 45 43 46 44 47 45 48 46 49 47 50 48 51 49 52 50 53 51...
output:
199988 199989 199989 199990 199990 199991 199991 199992 199992 199993 199993 199994 199994 199995 199995 199996 199996 199997 199997 199998 199998 199999 199999 200000 200000 200001 200001 200002 200002 200003 200003 200004 200004 200005 200005 200006 200006 200007 200007 200008 200008 200009 200009...
result:
ok single line: '199988 199989 199989 199990 19...46 384959 384960 384948 384961 '
Test #37:
score: 0
Accepted
time: 1934ms
memory: 63512kb
input:
199979 2 1 3 1 4 2 5 3 6 4 7 5 8 6 9 7 10 8 11 9 12 10 13 11 14 12 15 13 16 14 17 15 18 16 19 17 20 18 21 19 22 20 23 21 24 22 25 23 26 24 27 25 28 26 29 27 30 28 31 29 32 30 33 31 34 32 35 33 36 34 37 35 38 36 39 37 40 38 41 39 42 40 43 41 44 42 45 43 46 44 47 45 48 46 49 47 50 48 51 49 52 50 53 51...
output:
199978 199979 199979 199980 199980 199981 199981 199982 199982 199983 199983 199984 199984 199985 199985 199986 199986 199987 199987 199988 199988 199989 199989 199990 199990 199991 199991 199992 199992 199993 199993 199994 199994 199995 199995 199996 199996 199997 199997 199998 199998 199999 199999...
result:
ok single line: '199978 199979 199979 199980 19...39 399411 399411 399440 399441 '
Test #38:
score: 0
Accepted
time: 1455ms
memory: 64064kb
input:
199981 2 1 3 1 4 1 5 2 6 3 7 4 8 5 9 6 10 7 11 8 12 9 13 10 14 11 15 12 16 13 17 14 18 15 19 16 20 17 21 18 22 19 23 20 24 21 25 22 26 23 27 24 28 25 29 26 30 27 31 28 32 29 33 30 34 31 35 32 36 33 37 34 38 35 39 36 40 37 41 38 42 39 43 40 44 41 45 42 46 43 47 44 48 45 49 46 50 47 51 48 52 49 53 50 ...
output:
199980 199982 199982 199982 199984 199984 199984 199986 199986 199986 199988 199988 199988 199990 199990 199990 199992 199992 199992 199994 199994 199994 199996 199996 199996 199998 199998 199998 200000 200000 200000 200002 200002 200002 200004 200004 200004 200006 200006 200006 200008 200008 200008...
result:
ok single line: '199980 199982 199982 199982 19...84 393279 393281 393287 393287 '
Test #39:
score: 0
Accepted
time: 390ms
memory: 65464kb
input:
199981 2 1 3 1 4 1 5 2 6 3 7 4 8 5 9 6 10 7 11 8 12 9 13 10 14 11 15 12 16 13 17 14 18 15 19 16 20 17 21 18 22 19 23 20 24 21 25 22 26 23 27 24 28 25 29 26 30 27 31 28 32 29 33 30 34 31 35 32 36 33 37 34 38 35 39 36 40 37 41 38 42 39 43 40 44 41 45 42 46 43 47 44 48 45 49 46 50 47 51 48 52 49 53 50 ...
output:
199980 199982 199982 199982 199984 199984 199984 199986 199986 199986 199988 199988 199988 199990 199990 199990 199992 199992 199992 199994 199994 199994 199996 199996 199996 199998 199998 199998 200000 200000 200000 200002 200002 200002 200004 200004 200004 200006 200006 200006 200008 200008 200008...
result:
ok single line: '199980 199982 199982 199982 19...91 383291 383292 383293 383293 '
Test #40:
score: 0
Accepted
time: 1320ms
memory: 64380kb
input:
199984 2 1 3 1 4 1 5 2 6 3 7 4 8 5 9 6 10 7 11 8 12 9 13 10 14 11 15 12 16 13 17 14 18 15 19 16 20 17 21 18 22 19 23 20 24 21 25 22 26 23 27 24 28 25 29 26 30 27 31 28 32 29 33 30 34 31 35 32 36 33 37 34 38 35 39 36 40 37 41 38 42 39 43 40 44 41 45 42 46 43 47 44 48 45 49 46 50 47 51 48 52 49 53 50 ...
output:
199983 199985 199985 199985 199987 199987 199987 199989 199989 199989 199991 199991 199991 199993 199993 199993 199995 199995 199995 199997 199997 199997 199999 199999 199999 200001 200001 200001 200003 200003 200003 200005 200005 200005 200007 200007 200007 200009 200009 200009 200011 200011 200011...
result:
ok single line: '199983 199985 199985 199985 19...49 389950 389951 389951 389952 '
Test #41:
score: 0
Accepted
time: 1476ms
memory: 63528kb
input:
199984 2 1 3 1 4 1 5 2 6 3 7 4 8 5 9 6 10 7 11 8 12 9 13 10 14 11 15 12 16 13 17 14 18 15 19 16 20 17 21 18 22 19 23 20 24 21 25 22 26 23 27 24 28 25 29 26 30 27 31 28 32 29 33 30 34 31 35 32 36 33 37 34 38 35 39 36 40 37 41 38 42 39 43 40 44 41 45 42 46 43 47 44 48 45 49 46 50 47 51 48 52 49 53 50 ...
output:
199983 199985 199985 199985 199987 199987 199987 199989 199989 199989 199991 199991 199991 199993 199993 199993 199995 199995 199995 199997 199997 199997 199999 199999 199999 200001 200001 200001 200003 200003 200003 200005 200005 200005 200007 200007 200007 200009 200009 200009 200011 200011 200011...
result:
ok single line: '199983 199985 199985 199985 19...15 399615 399617 399617 399617 '
Test #42:
score: 0
Accepted
time: 1417ms
memory: 63960kb
input:
199989 2 1 3 1 4 1 5 1 6 2 7 3 8 4 9 5 10 6 11 7 12 8 13 9 14 10 15 11 16 12 17 13 18 14 19 15 20 16 21 17 22 18 23 19 24 20 25 21 26 22 27 23 28 24 29 25 30 26 31 27 32 28 33 29 34 30 35 31 36 32 37 33 38 34 39 35 40 36 41 37 42 38 43 39 44 40 45 41 46 42 47 43 48 44 49 45 50 46 51 47 52 48 53 49 5...
output:
199988 249987 249987 249987 249987 249989 249989 249989 249989 249991 249991 249991 249991 249993 249993 249993 249993 249995 249995 249995 249995 249997 249997 249997 249997 249999 249999 249999 249999 250001 250001 250001 250001 250003 250003 250003 250003 250005 250005 250005 250005 250007 250007...
result:
ok single line: '199988 249987 249987 249987 24...64 394965 394958 394970 394965 '
Test #43:
score: 0
Accepted
time: 414ms
memory: 64964kb
input:
199981 2 1 3 1 4 1 5 1 6 2 7 3 8 4 9 5 10 6 11 7 12 8 13 9 14 10 15 11 16 12 17 13 18 14 19 15 20 16 21 17 22 18 23 19 24 20 25 21 26 22 27 23 28 24 29 25 30 26 31 27 32 28 33 29 34 30 35 31 36 32 37 33 38 34 39 35 40 36 41 37 42 38 43 39 44 40 45 41 46 42 47 43 48 44 49 45 50 46 51 47 52 48 53 49 5...
output:
199980 249977 249977 249977 249977 249979 249979 249979 249979 249981 249981 249981 249981 249983 249983 249983 249983 249985 249985 249985 249985 249987 249987 249987 249987 249989 249989 249989 249989 249991 249991 249991 249991 249993 249993 249993 249993 249995 249995 249995 249995 249997 249997...
result:
ok single line: '199980 249977 249977 249977 24...58 387459 387459 387459 387460 '
Test #44:
score: 0
Accepted
time: 1311ms
memory: 64112kb
input:
199977 2 1 3 1 4 1 5 1 6 2 7 3 8 4 9 5 10 6 11 7 12 8 13 9 14 10 15 11 16 12 17 13 18 14 19 15 20 16 21 17 22 18 23 19 24 20 25 21 26 22 27 23 28 24 29 25 30 26 31 27 32 28 33 29 34 30 35 31 36 32 37 33 38 34 39 35 40 36 41 37 42 38 43 39 44 40 45 41 46 42 47 43 48 44 49 45 50 46 51 47 52 48 53 49 5...
output:
199976 249972 249972 249972 249972 249974 249974 249974 249974 249976 249976 249976 249976 249978 249978 249978 249978 249980 249980 249980 249980 249982 249982 249982 249982 249984 249984 249984 249984 249986 249986 249986 249986 249988 249988 249988 249988 249990 249990 249990 249990 249992 249992...
result:
ok single line: '199976 249972 249972 249972 24...36 392437 392437 392437 392438 '
Test #45:
score: 0
Accepted
time: 1441ms
memory: 63252kb
input:
199981 2 1 3 1 4 1 5 1 6 2 7 3 8 4 9 5 10 6 11 7 12 8 13 9 14 10 15 11 16 12 17 13 18 14 19 15 20 16 21 17 22 18 23 19 24 20 25 21 26 22 27 23 28 24 29 25 30 26 31 27 32 28 33 29 34 30 35 31 36 32 37 33 38 34 39 35 40 36 41 37 42 38 43 39 44 40 45 41 46 42 47 43 48 44 49 45 50 46 51 47 52 48 53 49 5...
output:
199980 249977 249977 249977 249977 249979 249979 249979 249979 249981 249981 249981 249981 249983 249983 249983 249983 249985 249985 249985 249985 249987 249987 249987 249987 249989 249989 249989 249989 249991 249991 249991 249991 249993 249993 249993 249993 249995 249995 249995 249995 249997 249997...
result:
ok single line: '199980 249977 249977 249977 24...94 399695 399695 399695 399696 '
Test #46:
score: 0
Accepted
time: 0ms
memory: 19892kb
input:
16 6 5 4 7 16 7 14 10 10 6 1 9 10 2 15 11 8 13 15 5 13 16 12 1 15 3 15 8 1 15 16 1 14 11 6 3 15 7 8 12 1 10 11 2 16 5 4 10 8 6 12 11 1 10 2 9 12 4 14 16 1 13 2
output:
19 24 30 22 17 17 22 19 32 18 25 25 19 20 16 19
result:
ok single line: '19 24 30 22 17 17 22 19 32 18 25 25 19 20 16 19 '
Test #47:
score: 0
Accepted
time: 348ms
memory: 71244kb
input:
200000 75181 178691 167132 24574 21481 90765 81460 60919 82245 108152 65683 173513 76902 84549 123226 91319 41694 165036 94669 192530 154076 153602 100902 20831 90175 147499 51312 16926 14772 167477 163013 122912 24100 55416 173417 128164 199861 186216 78608 76991 124298 91595 80825 119577 116094 13...
output:
50474638 50191810 69503436 54366029 53258199 60296221 52039784 63630859 58868296 82953818 78426866 93062178 83112557 93454169 75434369 78265902 54132728 47597410 82596185 89438443 91127263 53191470 50080591 48325373 47681641 71491673 66757053 88685300 59982978 77322154 65296864 49874706 88673812 784...
result:
ok single line: '50474638 50191810 69503436 543...982 47643953 69957694 70926955 '
Test #48:
score: 0
Accepted
time: 409ms
memory: 69272kb
input:
200000 188991 38536 19016 131514 34849 20659 146565 5563 127586 152943 139286 134818 165140 30444 41931 86603 26615 112397 5469 101689 26521 160202 21149 159878 45079 178089 131738 108012 177334 9239 90377 50876 196994 10435 91399 34143 27718 169370 83553 132616 178465 132491 162334 63031 180808 818...
output:
24993686 22535318 25093599 27418706 26197310 42204273 24869573 40511446 26130536 30057368 22369507 25394625 42596441 23199608 27299672 31766039 24448003 22320557 27297716 27659652 22792436 38332932 21704042 22267391 33757501 37465239 31090331 24057816 30435937 26269042 23201120 24094869 21714600 265...
result:
ok single line: '24993686 22535318 25093599 274...128 22141964 32257994 23383007 '
Test #49:
score: 0
Accepted
time: 460ms
memory: 66964kb
input:
200000 906 199746 107936 138177 62750 153929 59299 197264 68283 134308 168204 152703 87690 5885 182724 6013 60916 76081 80301 163580 84788 189716 168885 124983 54096 2802 106732 8500 163252 162533 6080 48703 187591 162568 45014 26781 68652 99032 25806 136034 67122 181202 177859 27996 193698 78737 17...
output:
32929020 34069370 40028545 37661564 38678342 30750107 33322391 43647777 32966166 34540745 56091894 30722580 31073744 45982654 30727586 32999951 30851744 30791018 43063835 31353181 59457024 30812724 36789879 51721870 31193313 33619943 38916209 31423361 34479112 35924734 51894027 57940165 40097310 322...
result:
ok single line: '32929020 34069370 40028545 376...609 56226588 30772657 47877102 '
Test #50:
score: 0
Accepted
time: 492ms
memory: 65912kb
input:
200000 40440 24070 53985 146625 68335 41905 37111 154568 87025 93999 166749 178229 90621 133195 94566 176393 80877 7309 51016 173297 84683 122464 50093 33531 29390 14574 144254 197157 59901 32183 136953 3045 144780 97707 142252 9994 161963 106725 67833 93692 66691 19180 11168 70696 174478 27071 3568...
output:
26783886 24103262 24341471 31558721 23646973 22561030 37838773 21854798 25488172 40353549 21486080 23151361 21678943 23151035 39659953 39278145 24645201 25186116 21622484 39624225 41304011 24995081 21578951 27711490 23503882 29970542 25286710 21544886 41336232 42304747 37134867 34719974 21513967 224...
result:
ok single line: '26783886 24103262 24341471 315...831 22937500 37317332 35645125 '
Test #51:
score: 0
Accepted
time: 533ms
memory: 64712kb
input:
200000 46568 142176 92040 6143 182603 189978 72891 67409 159519 191115 67289 86172 185549 11506 98061 180309 77000 107263 58451 198920 170080 170714 46827 3206 32273 27342 83368 67894 175680 1078 78837 62988 161130 70582 5223 133157 101436 14577 154937 193873 17799 162737 23687 54641 85214 82353 193...
output:
33798263 32555933 48157520 43134079 32532199 50632136 49287897 56378466 42412373 33334251 44502560 33503605 36741434 55532750 35496162 32950017 34702169 56715631 42046007 33522284 36821057 64726295 34295338 36626392 45068949 45658390 40083911 33131584 47703579 47126418 41396118 42826295 40135185 583...
result:
ok single line: '33798263 32555933 48157520 431...765 46003035 32567705 33923064 '
Test #52:
score: 0
Accepted
time: 567ms
memory: 63464kb
input:
200000 51240 130378 64520 44156 59560 155045 51704 99909 59561 134357 126256 63666 15949 140681 72887 126011 170282 13437 57032 131896 185862 98012 95093 141872 183438 41646 64877 11578 94960 153354 41961 196982 183878 180510 44417 102166 184835 136493 122867 168934 183074 115227 34126 58709 126803 ...
output:
24103329 18147085 17013747 18290357 20541449 19479085 25359019 25641877 28533173 19426147 26188760 21312766 20714945 23031381 20633574 17122927 22665153 21993733 18528212 20431080 17741588 18150951 33210156 29200169 17201878 20185600 25179090 32284344 25471417 19801285 18042747 19661852 17046147 285...
result:
ok single line: '24103329 18147085 17013747 182...236 28034076 21443078 33448613 '
Test #53:
score: 0
Accepted
time: 754ms
memory: 62744kb
input:
200000 99719 120749 26467 12087 64651 169043 103895 184334 118838 55887 75096 145169 182647 90953 129978 141482 10983 185683 96556 30195 16919 25618 197146 54090 143967 159127 133629 167436 108954 105218 129783 115593 148324 58557 125717 70523 147382 32019 90141 77494 71835 14416 32734 108007 169625...
output:
4540663 4671456 4428939 5535385 6892497 5557766 7408781 7410797 4275469 4194013 4158930 5352076 4606566 6293647 4412235 6511061 7420271 5893908 5945178 4670589 6227712 4356763 4735789 4239261 5558620 6429973 7060108 5150232 6201608 6290625 4361744 6511328 4485881 7060130 7219599 7961307 4325850 6159...
result:
ok single line: '4540663 4671456 4428939 553538...195899 5352787 6260023 6734375 '
Test #54:
score: 0
Accepted
time: 938ms
memory: 62248kb
input:
200000 39006 155355 59936 58989 114072 52126 144417 130838 192407 125631 98060 126007 63946 143554 97804 5617 179450 175794 135854 130826 141387 199480 84980 116863 107663 189000 148102 30432 182946 27437 113614 13034 82327 164808 48176 58845 147970 62823 189143 186194 11550 183879 93591 122219 1449...
output:
800775 621521 690096 695843 715598 824539 563225 932567 798424 760340 696182 923151 684252 799804 796222 752250 799208 797506 796713 922821 755995 689309 799710 923878 759527 690023 925395 739686 756049 922539 1105590 923584 667962 730115 752095 800875 922109 756461 751538 796525 932456 897174 95477...
result:
ok single line: '800775 621521 690096 695843 71...75 682165 587557 756755 698636 '
Test #55:
score: 0
Accepted
time: 1309ms
memory: 62420kb
input:
200000 66301 173363 129318 127908 128408 164206 12510 80814 80498 147845 185443 78596 153018 23013 139590 103971 42588 68867 89578 101577 73679 13597 71140 188721 118546 118625 121316 30257 178132 133021 28694 128971 55640 177671 40134 81023 133914 50892 175589 367 94401 129808 59739 185865 197921 9...
output:
417997 415952 416904 415957 416020 418169 409679 412301 614369 413756 416345 415805 416075 412592 424787 418842 408384 418210 413973 818569 417973 412425 413548 411639 414520 623624 615600 413791 417718 416669 415289 404658 454610 433763 398469 550769 416076 416056 405714 423859 415449 415930 415310...
result:
ok single line: '417997 415952 416904 415957 41...07 411842 617991 408427 409265 '
Test #56:
score: 0
Accepted
time: 343ms
memory: 72044kb
input:
200000 61396 81570 55536 113950 46900 141787 43935 87423 194884 117890 20095 131408 134063 62971 172244 47759 25833 30615 167427 63421 122035 15558 157184 113222 27992 192054 100424 67032 66630 153777 185783 42049 115814 71168 125770 19171 88777 5184 11269 56730 51095 36238 154829 14343 3544 175070 ...
output:
1125442347 897306694 1001004565 649092624 723128284 631343757 704511677 734670273 882958790 777386128 629240951 1049280047 639632957 832483529 1104153491 1192296126 1253461863 633258056 795563764 775937775 917503230 641793821 1007312973 1024531355 726813868 967214610 911983580 797826440 629818720 69...
result:
ok single line: '1125442347 897306694 100100456... 829324349 804021626 644347161 '
Test #57:
score: 0
Accepted
time: 0ms
memory: 20024kb
input:
64 17 54 50 47 7 55 13 64 41 5 40 16 26 61 3 49 38 23 19 3 47 53 58 9 18 21 23 41 39 18 16 12 26 51 2 57 36 17 44 48 10 14 50 32 14 9 60 5 1 17 20 22 13 50 17 30 64 42 49 50 17 12 57 12 56 20 12 20 18 28 59 16 34 6 45 23 41 34 24 18 44 4 31 63 13 23 45 29 5 26 8 14 9 25 7 31 39 27 14 13 37 7 18 14 4...
output:
174 120 120 113 99 124 98 121 99 117 119 81 71 82 121 114 112 95 182 113 140 121 89 157 125 103 120 117 184 122 114 125 124 115 117 117 117 151 116 119 91 124 131 109 122 125 124 109 78 74 106 124 129 174 119 121 108 128 121 124 121 142 120 108
result:
ok single line: '174 120 120 113 99 124 98 121 ...08 128 121 124 121 142 120 108 '
Test #58:
score: 0
Accepted
time: 441ms
memory: 67560kb
input:
200000 151798 54121 50378 178642 145024 73817 137584 180522 105434 166414 95728 89567 81830 36549 195511 54760 55208 127964 33742 181666 178737 123474 37713 158296 52229 192513 2285 190186 19962 58300 79487 196840 151032 194269 114019 3746 128197 4441 99945 191537 105525 107799 72341 117203 36561 14...
output:
10634193 15723004 16345762 14071076 12822659 11416194 12325965 16025945 12852678 10658740 10567204 11672494 15537903 13442275 10993458 14286284 16957123 18409808 17915298 11611947 10655142 17218735 12516512 12683865 18002109 10632883 16504736 15533329 12299631 10881149 13932098 18275622 13209522 105...
result:
ok single line: '10634193 15723004 16345762 140...173 10659417 10615978 14045553 '
Test #59:
score: 0
Accepted
time: 444ms
memory: 64516kb
input:
200000 70195 37550 90611 70195 52647 70195 119470 70195 68644 70195 70195 78334 120998 70195 26479 70195 70195 36317 70195 138045 70195 15345 111105 70195 50529 70195 70195 171759 114026 70195 70195 28292 70195 107531 70195 186922 108409 70195 164172 70195 70195 147304 70195 125251 70195 61283 70195...
output:
399996 399995 399997 399996 399997 399997 399995 399995 399996 399996 399996 399997 399996 399997 399993 399994 399996 399996 399996 399997 399994 399993 399995 399995 399996 399994 399996 399996 399996 399997 399996 399996 399995 399996 399997 399994 399995 399996 399996 399997 399995 399993 399997...
result:
ok single line: '399996 399995 399997 399996 39...97 399994 399995 399997 399996 '
Test #60:
score: 0
Accepted
time: 522ms
memory: 65376kb
input:
200000 87477 195400 173272 39212 32721 141918 144675 39203 91467 24819 134447 99751 173513 74604 192792 190552 189104 80092 122421 37724 112794 8299 7731 197135 99749 182732 70522 139763 74047 115370 30624 61605 168403 56560 50864 89579 100515 21011 160135 149767 64663 148316 199277 94803 31445 4914...
output:
6194693 3363282 5258336 3093303 3965440 4665391 4486150 3931493 3010307 3121102 3565241 5942965 6160943 3766569 3360814 3889613 5457213 5515010 3467278 5936184 2834265 5759750 4440628 3005431 3484870 5085028 6137698 3669788 4671712 5655091 3235721 3553236 4325772 3673265 3911328 3769367 3352780 4219...
result:
ok single line: '6194693 3363282 5258336 309330...918987 3398829 5678981 2928525 '
Test #61:
score: 0
Accepted
time: 637ms
memory: 63268kb
input:
200000 85439 30600 73628 143172 94528 56713 60433 11700 162850 1717 67215 114048 125603 14417 136543 67393 27773 172979 3306 173392 151603 90063 165745 140576 37845 117956 193012 21945 154586 129677 140083 49377 113109 117037 143624 94767 109404 86771 24880 161247 114438 160962 110924 103481 39580 8...
output:
2583731 3524621 2376028 3528726 2487799 2387709 2637106 3186771 2205471 2569658 4743262 3503474 2325163 3056478 4050326 2409235 3488850 2304502 2396363 3583287 2596711 2237203 2926833 3638708 2576197 2775843 3453905 2486956 2307381 2890969 3757566 3693466 2915172 3671685 2479833 3016672 3811964 2217...
result:
ok single line: '2583731 3524621 2376028 352872...501726 2552418 3519939 4025430 '
Test #62:
score: 0
Accepted
time: 651ms
memory: 63592kb
input:
200000 101253 133884 161023 179465 146180 167585 73836 167629 181637 61177 153518 90494 180411 128220 143663 52464 45744 103680 190838 186745 115678 180066 71265 98439 134376 61236 3313 191788 6017 42295 146020 169428 3015 82222 118310 169273 195832 80228 80846 13936 150889 80201 46688 63709 117472 ...
output:
3022541 2863104 2050833 2200313 2492308 2778408 2065196 1630179 2848659 1971695 1616699 1726806 1873549 2154897 1692391 3118750 2347576 1915477 1844188 1795856 3043729 1867794 2616673 3150023 1710245 2230556 2078113 1640400 2261684 2761081 1636800 1662700 2183496 2735993 2760334 2563027 1716458 1937...
result:
ok single line: '3022541 2863104 2050833 220031...728652 1843756 1627820 1745386 '
Test #63:
score: 0
Accepted
time: 534ms
memory: 65108kb
input:
200000 71474 141281 21131 190770 166504 43257 14359 51681 132595 102961 198412 178537 178888 165923 79682 24117 51450 133748 188373 199835 129666 132794 29485 14931 5503 175213 97509 5223 179715 169606 79431 135639 51764 28576 127204 97752 164765 29782 112288 188592 45105 21766 16081 165872 119622 7...
output:
3607100 4071362 4860306 3420680 3520295 4551372 6702346 7138062 4110507 3367639 3405329 4508598 4657321 5064106 6405449 3453667 4076134 3664077 3570811 3413046 3936113 3908705 3979964 5050095 5859751 4374096 3444629 4722548 3475687 3650429 3661367 4443784 3947781 3621545 4186669 5926952 4225527 3559...
result:
ok single line: '3607100 4071362 4860306 342068...666329 5738735 4091200 4788132 '
Test #64:
score: 0
Accepted
time: 654ms
memory: 63884kb
input:
200000 12647 114265 89650 71121 48795 174687 55878 55011 41042 70046 128974 78729 169784 114391 165509 1199 148948 75775 73828 130475 8676 17475 77586 107518 28170 41745 45184 115162 36099 177438 94873 80232 14199 127887 124894 98540 131980 132925 44456 102588 31296 124857 73907 39176 83498 65717 14...
output:
2740217 2277647 3831876 3229121 3390510 2220434 4196031 2553746 2277846 2646843 3894033 2293704 2832567 2451446 3402180 4451576 3917847 2620579 3439305 2887617 3076165 4534977 2911030 3604015 3787194 2450157 2511552 2313462 2985103 3521182 3387539 2896914 3378313 2258840 3957508 2346163 3884895 2391...
result:
ok single line: '2740217 2277647 3831876 322912...727473 3294093 2854580 2887201 '
Test #65:
score: 0
Accepted
time: 723ms
memory: 62744kb
input:
200000 9527 94152 146053 122142 151175 53726 137277 46273 21925 199504 34754 133663 115276 169024 164032 169864 53412 199735 32570 168773 8012 9680 40920 48052 70121 197701 137933 31670 157764 183660 95295 142880 124013 113011 169527 16616 162734 109694 99587 159405 70761 151544 177595 47602 8193 13...
output:
2130784 1086498 1088077 1886042 1359271 1505763 1980920 1141795 1187148 2529020 1374164 1655559 1408724 1325279 1415417 2202828 1449186 1330929 1113980 2179256 1693369 1428522 1451766 1142163 1369537 1442761 1678893 1124124 2131912 1124076 2086655 1478305 2070080 1900113 1383528 1304718 1738608 1837...
result:
ok single line: '2130784 1086498 1088077 188604...340715 1685394 1413848 1501135 '
Test #66:
score: 0
Accepted
time: 600ms
memory: 63336kb
input:
200000 64321 79007 134698 25912 55202 156769 43677 165615 163493 56112 52785 154943 94004 154030 3222 10824 173904 96601 192767 69328 37045 55584 166187 137509 91232 6047 1725 33224 198582 146070 73087 154719 130684 157300 80921 7165 56886 10897 165636 439 2179 109630 53895 20647 75011 179398 113060...
output:
3216415 4003185 3188637 5671920 5085110 4580285 6286291 5675527 5726760 4954015 3658799 3256399 3229926 4452066 4320545 3299316 3565976 4323100 5182319 6038849 3725487 5336971 3478746 3110613 6249568 3673952 3324042 4041492 3488684 3192732 4749858 6006522 3130167 4372954 4584937 3201987 6495566 6567...
result:
ok single line: '3216415 4003185 3188637 567192...269668 3279079 3654056 4423055 '
Test #67:
score: 0
Accepted
time: 668ms
memory: 62808kb
input:
200000 132634 25975 167323 47819 53039 40655 32742 109181 17217 95146 176891 182393 34915 10165 120939 128624 6787 193796 180678 135986 190374 197501 195634 68495 3541 91174 114834 78593 105347 193760 61618 155366 156146 81639 24804 47578 143407 171294 127377 148107 10921 137552 182198 115349 133205...
output:
2231643 2015504 1884740 1457340 1974987 1413303 1242859 1336960 2296406 2216740 2001345 1477939 1831882 2079298 2263830 2121544 1848236 1480732 1728727 1652652 2044124 1536902 2882734 2991491 1462343 2022910 2236041 2102252 1339638 2440196 2336095 1998648 1808796 1501717 1337806 1396482 1843642 1999...
result:
ok single line: '2231643 2015504 1884740 145734...443435 1243645 1723962 1666617 '
Test #68:
score: 0
Accepted
time: 3ms
memory: 20032kb
input:
256 175 31 81 13 225 111 184 187 59 221 79 103 90 86 46 198 49 212 199 233 46 251 186 246 167 235 232 55 174 214 172 179 43 199 179 72 166 104 129 21 208 66 111 146 242 174 170 71 182 59 161 137 15 26 103 150 148 157 3 73 173 202 1 65 167 121 40 114 242 239 83 207 111 223 1 60 218 45 174 101 249 126...
output:
454 514 464 760 507 773 519 549 529 308 503 529 338 492 510 392 512 512 749 502 494 347 296 514 481 496 661 515 526 507 740 617 532 490 515 493 746 518 518 519 529 506 308 305 504 502 509 510 580 554 519 533 543 549 467 509 778 520 510 506 496 760 520 756 518 515 507 518 497 548 496 523 493 514 475 ...
result:
ok single line: '454 514 464 760 507 773 519 54...20 749 468 527 516 527 499 494 '
Test #69:
score: 0
Accepted
time: 779ms
memory: 62212kb
input:
200000 15416 7979 69244 101223 126238 160437 49943 57191 88680 24539 1779 54042 192116 99497 187439 82878 95673 172817 11996 57391 104713 174935 20305 30617 88902 174205 58022 81908 65133 128347 176040 44735 148361 38533 115777 97657 160652 58483 185632 57972 11213 26084 93870 190215 175218 190951 1...
output:
1180731 1056371 1612134 1378262 1624527 1012776 1112859 1566211 1310536 1714743 1407847 1742571 1671536 1740797 1149290 2027093 1368592 1090640 1075085 1274189 1609461 1267924 1607220 1037533 1532439 1740735 1184763 1189321 1362621 1021988 1405653 1511438 1631634 1517605 1263317 1761842 1371378 1144...
result:
ok single line: '1180731 1056371 1612134 137826...012821 1367193 1140120 1062140 '
Test #70:
score: 0
Accepted
time: 440ms
memory: 63524kb
input:
200000 180392 39292 71358 43871 56360 42180 121413 187197 156785 26595 14838 123219 117993 149881 43528 109763 99332 73419 65699 140906 65071 93546 147027 68576 174066 137502 17373 136777 124039 32023 11506 90063 43646 94883 49947 140393 126263 87521 150742 61123 72228 72191 114890 80911 130520 1567...
output:
819009954 1372137863 1467951618 760700605 1242057328 990053065 828093652 886399518 1027366858 991040315 1008488672 1055479826 1133487270 958645367 816904419 1069406692 1016404627 1654994970 1404472528 929007763 816878877 1140544525 780665799 848605797 1137730367 933131651 1483065427 1040799047 10823...
result:
ok single line: '819009954 1372137863 146795161...591165731 766543810 1218459840 '
Test #71:
score: 0
Accepted
time: 525ms
memory: 62740kb
input:
200000 5592 20651 175675 154967 5456 67803 92451 32979 193060 29325 90651 114785 21845 168241 117360 168300 119716 14151 177116 173612 36977 92239 119341 36196 171998 53503 18495 140811 75886 23558 34218 11994 161621 146769 16036 55434 33487 67102 50733 145002 52418 151429 72220 110981 168111 142013...
output:
128676808 127282331 174061914 169744068 141220429 152601663 244458823 221032841 197728057 190236367 141356272 158291296 128817307 140014014 136637098 203753576 127376689 128598671 172487392 166103817 139273310 127323316 184668159 202070964 247751358 136278435 236391766 167240430 218684964 169659120 ...
result:
ok single line: '128676808 127282331 174061914 ... 127626279 243581911 170714245 '
Test #72:
score: 0
Accepted
time: 0ms
memory: 20388kb
input:
1024 283 440 599 501 628 55 268 211 368 490 134 50 348 905 982 71 422 790 442 219 896 285 1013 217 319 30 85 194 1 50 922 722 81 514 635 572 556 633 304 910 720 750 209 476 289 728 109 721 397 919 29 677 889 151 981 80 740 1001 402 168 415 693 970 548 213 840 983 589 893 875 191 132 191 568 482 691 ...
output:
2122 2188 2114 3112 2095 1791 2131 2103 2113 1957 2115 2087 2170 2185 2172 2148 2339 3238 2341 2107 2481 2098 2099 2137 2150 2116 3152 2116 2121 2121 2165 2112 2127 2084 2136 1935 2134 2979 2112 2178 1828 2106 2146 1936 2148 2099 2137 2138 2071 2090 2086 2123 2125 2087 3124 2122 2223 2085 2156 2165 ...
result:
ok single line: '2122 2188 2114 3112 2095 1791 ... 2122 1586 2117 2103 2074 2082 '
Test #73:
score: 0
Accepted
time: 16ms
memory: 20628kb
input:
4096 1984 1595 1539 3196 1286 733 2311 1347 2222 266 726 1088 211 3356 2752 604 1173 4010 1391 393 3752 4094 2487 3589 2985 475 3497 2425 2466 1235 32 3265 1583 3837 722 3656 2423 257 2261 173 3290 913 2209 2489 3807 3594 3132 3440 3721 1134 2628 1255 2764 615 3089 290 1513 688 3231 1508 2379 3955 2...
output:
8451 8920 8299 8515 8448 6496 8515 8930 8713 10932 8545 8503 8493 8558 8183 8493 8475 8412 8704 8577 8611 9660 8389 8455 8503 8436 8574 8708 8800 8477 8486 8361 8915 8443 8442 8466 8656 8680 8649 8504 8501 8382 8555 8545 8710 8508 10945 8413 16688 8617 6989 7669 8548 8059 8494 8704 12542 8613 8535 8...
result:
ok single line: '8451 8920 8299 8515 8448 6496 ... 8509 8566 8520 8404 8574 8406 '
Extra Test:
score: 0
Extra Test Passed