QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#89181 | #5249. Bandits | whatever | AC ✓ | 1327ms | 101240kb | C++14 | 3.5kb | 2023-03-19 10:44:03 | 2023-03-19 10:44:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
bool Mbe;
constexpr int K = 17;
constexpr int N = 1e5 + 5;
ll dep[N];
int u[N], v[N], w[N];
int n, q, dn, lg[N], dfn[N], mi[K][N];
struct edge {
int id, to, val;
};
vector<edge> e[N];
int get(int x, int y) {
return dep[x] < dep[y] ? x : y;
}
int lca(int u, int v) {
if(u == v) return u;
if((u = dfn[u]) > (v = dfn[v])) swap(u, v);
int d = lg[v - u++];
return get(mi[d][u], mi[d][v - (1 << d) + 1]);
}
ll dis(int u, int v) {
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
ll dise(int x, int e) {
return max(dis(x, u[e]), dis(x, v[e]));
}
void dfs(int id, int ff) {
mi[0][dfn[id] = ++dn] = ff;
for(edge _ : e[id]) {
int it = _.to;
if(it != ff) dep[it] = dep[id] + _.val, dfs(it, id);
}
}
int R, sz[N], mx[N], vis[N];
int fa[N], ddep[N];
void findr(int id, int ff, int tot) {
sz[id] = 1, mx[id] = 0;
for(edge _ : e[id]) {
int it = _.to;
if(it == ff || vis[it]) continue;
findr(it, id, tot), sz[id] += sz[it];
mx[id] = max(mx[id], sz[it]);
}
mx[id] = max(mx[id], tot - sz[id]);
if(mx[id] < mx[R]) R = id;
}
vector<pair<ll, int>> c[N], cfa[N];
void findv(int id, int ff, int anc) {
for(edge _ : e[id]) {
int it = _.to;
if(it == ff) continue;
c[anc].push_back({dis(anc, it), 0});
if(fa[anc]) cfa[anc].push_back({dise(fa[anc], _.id), 0});
if(!vis[it]) findv(it, id, anc);
}
}
void add(int id, ll x, vector<auto> &c) {
if(x < 0) return;
x = upper_bound(c.begin(), c.end(), make_pair(x, N)) - c.begin() - 1;
while(x) c[x].second++, x -= x & -x;
}
ll query(int id, ll x, vector<auto> &c) {
x = lower_bound(c.begin(), c.end(), make_pair(x, -N)) - c.begin();
int s = 0;
while(x < c.size()) s += c[x].second, x += x & -x;
return s;
}
void divide(int id) {
vis[id] = 1;
c[id].push_back({-LONG_LONG_MAX, 0});
cfa[id].push_back({-LONG_LONG_MAX, 0});
findv(id, 0, id);
sort(c[id].begin(), c[id].end());
sort(cfa[id].begin(), cfa[id].end());
for(edge _ : e[id]) {
int it = _.to;
if(vis[it]) continue;
R = 0, findr(it, id, sz[it]);
fa[R] = id, ddep[R] = ddep[id] + 1;
divide(R);
}
}
void add(int x, int R) {
for(int u = x; u; u = fa[u]) {
add(u, R - dis(x, u), c[u]);
if(fa[u]) add(u, R - dis(x, fa[u]), cfa[u]);
}
}
int query(int id) {
int x = ddep[u[id]] > ddep[v[id]] ? u[id] : v[id];
int ans = 0;
for(int u = x; u; u = fa[u]) {
ans += query(u, dise(u, id), c[u]);
if(fa[u]) ans -= query(u, dise(fa[u], id), cfa[u]);
}
return ans;
}
bool Med;
int main() {
fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#ifdef ALEX_WEI
FILE* IN = freopen("1.in", "r", stdin);
FILE* OUT = freopen("1.out", "w", stdout);
#endif
cin >> n;
for(int i = 1; i < n; i++) {
cin >> u[i] >> v[i] >> w[i];
e[u[i]].push_back({i, v[i], w[i]});
e[v[i]].push_back({i, u[i], w[i]});
}
dfs(1, 0);
for(int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
for(int i = 1; i <= lg[n]; i++)
for(int j = 1; j + (1 << i) - 1 <= n; j++)
mi[i][j] = get(mi[i - 1][j], mi[i - 1][j + (1 << i - 1)]);
mx[0] = N, findr(1, 0, n);
divide(R);
cin >> q;
for(int i = 1; i <= q; i++) {
char op;
int u, v;
cin >> op >> u;
if(op == '+') cin >> v, add(u, v);
else cout << query(u) << "\n";
}
cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1228ms
memory: 97392kb
input:
100000 2670 75097 4080 87477 75802 1712 51835 36626 2883 19412 25923 5852 23976 19312 2520 82536 19514 2492 27160 66601 4483 99087 15088 3504 47050 58820 2964 37063 5696 9901 7717 1496 4891 79136 5448 4340 22575 81285 9289 96280 3803 9877 41980 32139 2855 44236 64938 3298 5983 99947 9666 95856 62545...
output:
0 0 0 2 2 5 2 2 3 4 4 7 8 9 11 10 14 12 12 10 11 10 10 9 10 11 11 9 15 11 14 13 14 16 11 17 15 13 15 14 14 20 15 20 22 22 20 17 23 23 24 29 24 26 30 31 36 28 37 39 35 34 45 39 46 45 43 46 42 49 44 50 43 47 52 50 49 57 51 56 61 58 68 66 69 69 61 63 67 63 72 74 78 72 73 78 77 73 85 76 86 82 85 76 82 8...
result:
ok 50000 lines
Test #2:
score: 0
Accepted
time: 767ms
memory: 68888kb
input:
100000 30038 18547 1594 65857 34063 4575 36600 72585 2328 99199 77595 1590 64257 48199 589 72301 40302 5083 69474 97536 606 60079 67381 9331 65982 39033 205 84122 65285 8508 18167 44905 3704 93490 94986 5941 27155 46374 6616 36232 62969 2212 79807 68652 7199 87352 59101 6880 94571 53224 3552 63610 8...
output:
0 1 3 3 3 3 4 6 10 10 12 14 14 16 18 19 19 19 19 22 22 23 23 23 23 24 25 26 26 26 26 26 26 28 31 31 31 31 31 34 34 36 40 41 41 42 42 42 42 42 44 44 44 47 48 48 48 48 48 48 48 48 48 49 50 50 53 54 54 55 55 56 56 56 56 56 59 62 62 62 62 62 62 62 62 62 62 63 65 67 69 69 69 73 73 73 74 76 76 76 76 76 79...
result:
ok 50000 lines
Test #3:
score: 0
Accepted
time: 1244ms
memory: 89980kb
input:
100000 61878 94907 27495452 40498 66053 163324081 9987 91760 269034612 88613 6169 634714395 87422 83687 263182872 22328 64374 595886322 57437 38976 201931120 75020 26926 516189886 88639 96262 269100132 88285 44915 173237252 88407 91931 174315082 12843 50312 641940581 13297 52746 120211351 89089 4638...
output:
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 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 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 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 50000 lines
Test #4:
score: 0
Accepted
time: 1000ms
memory: 89888kb
input:
100000 45843 69600 747867718 13793 70429 681785830 79985 74443 517803908 38369 67457 257059055 49843 59820 901603712 26439 25214 598556764 10275 5998 613157018 13517 10279 61272074 45577 49749 153772596 30727 68824 827689136 21752 9334 936611496 49173 73121 899562409 67808 9217 665070707 38351 13721...
output:
0 0 0 0 3 0 0 0 0 1 1 0 4 2 0 1 1 0 2 0 3 1 0 0 0 1 1 0 1 2 1 0 0 1 0 1 1 2 2 2 0 0 0 0 2 0 1 1 0 0 3 2 0 0 0 0 0 1 0 1 0 1 0 0 0 2 2 2 0 0 1 0 0 1 1 0 0 0 1 3 2 0 0 0 0 0 0 2 2 0 0 0 0 3 2 3 1 1 0 0 3 1 1 0 2 1 1 2 1 0 1 2 1 0 4 2 1 3 1 1 1 0 0 0 0 1 3 1 1 1 2 1 2 1 0 1 1 0 0 0 2 0 0 0 3 3 1 0 1 1 ...
result:
ok 50000 lines
Test #5:
score: 0
Accepted
time: 1ms
memory: 10840kb
input:
10 1 6 50 5 7 60 10 7 57 1 7 7 8 10 71 9 8 66 1 3 79 9 4 92 8 2 41 8 ? 5 ? 2 + 5 159 ? 7 ? 4 + 9 184 ? 7 + 3 291
output:
0 0 1 1 1
result:
ok 5 lines
Test #6:
score: 0
Accepted
time: 1157ms
memory: 92616kb
input:
100000 34346 47902 18 27392 33766 77 6756 26094 49 22936 48815 19 5650 6237 49 30025 40524 59 54595 38103 73 31226 14746 66 90535 30187 7 31954 7326 41 88688 84625 35 87060 2678 4 51031 33729 53 78866 33403 76 16783 75299 96 96244 52833 50 72746 8315 62 3610 74402 43 5479 75776 55 98976 97524 74 261...
output:
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 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 1 0 2 0 0 3 0 1 0 1 0 2 3 0 0 0 0 0 0 1 3 0 1 0 0 1 0 0 1 0 2 2 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 1 0 0 1 2 3 0 0 1 1 2 1 1 2 0 0 1 0 0 3 1 0 0 1 2 1 1 0 1 0 1 1 0 2 0 1 ...
result:
ok 50000 lines
Test #7:
score: 0
Accepted
time: 1223ms
memory: 92604kb
input:
100000 64148 54183 29 11068 35332 64 25618 18806 90 77040 76732 10 84812 90880 38 42283 75749 18 16322 30644 94 36973 59934 83 29747 75832 83 65108 11462 34 56098 73933 71 13086 78104 88 61180 33475 85 14006 4857 5 3734 96760 71 71250 14549 2 33684 24761 9 14693 12183 86 16730 80793 35 4985 57321 20...
output:
0 0 3 3 3 5 8 10 10 11 12 13 12 13 13 13 14 14 15 16 16 18 17 21 23 22 23 22 22 26 26 33 36 37 36 36 37 36 38 39 41 38 39 42 43 42 42 46 46 46 48 53 49 52 53 54 53 56 58 57 54 59 59 58 58 59 59 55 58 62 58 62 62 60 60 68 68 65 64 70 69 70 72 78 78 76 76 76 77 80 79 80 82 80 84 85 84 86 89 87 83 90 9...
result:
ok 50000 lines
Test #8:
score: 0
Accepted
time: 1259ms
memory: 92136kb
input:
100000 14082 229 36 27210 94270 83 4742 68213 50 87953 67081 92 51909 51726 24 90045 60667 69 24283 69653 69 315 54923 19 44878 20782 60 65714 37239 18 18550 90268 99 90511 90267 26 74527 52573 9 44461 37153 92 94712 75548 81 54222 86266 71 99559 95348 72 19824 84320 53 57415 91290 10 1848 64264 73 ...
output:
29569 22292 26968 29422 29480 29605 28379 19743 24389 24969 24814 19826 28407 22403 29124 28900 24214 21261 20969 29297 22382 27345 16938 24009 21936 21580 28754 27089 26016 28921 28981 26058 26175 17364 29296 20002 27815 29591 23866 26980 26606 20345 27293 19831 20130 18982 27761 25353 21109 16845 ...
result:
ok 50000 lines
Test #9:
score: 0
Accepted
time: 2ms
memory: 10776kb
input:
10 5 9 19 10 7 2 7 8 62 4 6 79 1 4 34 2 10 44 2 3 27 6 3 52 1 9 65 8 + 7 67 ? 2 + 2 15 ? 5 ? 5 ? 5 + 9 6 ? 9
output:
1 0 0 0 0
result:
ok 5 lines
Test #10:
score: 0
Accepted
time: 1229ms
memory: 100796kb
input:
100000 76345 58764 90 38618 20579 17 64447 62815 58 59951 76798 55 74438 62576 95 53180 2222 89 11870 17020 38 39889 48984 74 16333 40563 97 25845 69446 58 5310 92817 62 3253 1870 7 89005 49525 84 82761 65333 77 84354 79477 21 580 24067 88 37079 78987 1 71193 72699 69 74616 30155 89 57080 85169 71 6...
output:
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 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 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 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 ...
result:
ok 50000 lines
Test #11:
score: 0
Accepted
time: 1273ms
memory: 101240kb
input:
100000 93170 87268 37 92583 41762 3 93445 95084 53 73369 81234 79 22891 43413 79 16715 69518 7 24171 20852 78 85174 42270 89 66924 67254 49 43354 42747 38 49859 42160 93 40042 50857 22 4048 65749 86 24257 79582 28 87393 44008 99 72905 724 0 91334 97136 21 94537 97499 73 25630 70522 17 60066 15405 10...
output:
0 0 0 0 1 1 1 1 3 4 3 4 4 4 7 7 7 7 7 8 7 9 10 10 10 10 10 14 15 15 17 17 17 17 17 17 19 18 19 23 26 26 24 27 26 29 28 30 30 26 31 35 36 37 38 39 40 41 40 42 40 38 36 42 36 39 40 38 40 50 51 50 54 42 44 56 45 56 59 61 51 63 61 68 62 67 62 69 55 70 68 70 72 72 74 65 66 60 67 74 79 81 67 76 71 90 88 9...
result:
ok 50000 lines
Test #12:
score: 0
Accepted
time: 1327ms
memory: 100876kb
input:
100000 19572 74611 8 48607 74319 78 93319 98288 59 52549 90890 45 94797 90913 3 39349 35315 61 38406 98513 80 93016 86528 75 8738 42441 86 30903 41462 74 10393 85631 20 42211 49293 9 94579 14667 32 12354 61859 3 74498 17678 30 73444 85087 70 66415 69027 94 43638 69756 59 39651 46403 85 85460 86047 9...
output:
9967 10077 10052 9942 10077 10159 9742 9523 8936 9982 9997 9033 10148 10124 10094 10155 10003 10077 10088 10116 9958 10208 6409 8007 10173 10046 9956 10078 8473 10167 9797 6675 10136 10067 10098 10107 10033 10138 9480 7747 10040 9954 10013 8801 9980 5539 9953 10077 10072 9992 10040 10153 10134 7920 ...
result:
ok 50000 lines
Test #13:
score: 0
Accepted
time: 1ms
memory: 10816kb
input:
10 2 9 4 7 9 90 9 6 18 9 3 17 9 4 36 8 9 4 9 5 11 9 1 99 9 10 75 10 + 2 5 + 6 75 ? 8 + 10 14 ? 4 ? 2 ? 4 + 5 96 ? 8 + 10 53
output:
0 1 0 1 0
result:
ok 5 lines
Test #14:
score: 0
Accepted
time: 194ms
memory: 36536kb
input:
100000 49647 87470 68018 49647 66838 706542 90701 49647 804547 49647 49695 565349 89649 49647 58330 85202 49647 867857 49647 36014 819333 72467 49647 976326 49647 79763 583342 70175 49647 517474 49647 33568 520456 1985 49647 345782 66678 49647 972856 49647 68759 529647 49647 74524 568714 61394 49647...
output:
2 2 3 3 0 0 3 1 7 7 7 0 0 8 6 8 6 4 7 1 6 8 4 7 6 14 5 10 0 4 13 3 14 1 15 7 12 5 3 7 5 15 18 7 4 8 0 3 22 8 5 5 2 16 3 15 6 0 14 5 26 27 3 4 4 28 9 4 0 4 21 5 21 33 3 30 4 14 13 10 14 21 8 36 6 27 38 10 5 32 12 7 0 35 7 7 10 17 10 38 5 2 0 5 5 37 2 45 44 0 44 39 8 4 31 11 2 20 31 10 37 0 0 16 12 1 ...
result:
ok 50000 lines
Test #15:
score: 0
Accepted
time: 157ms
memory: 36308kb
input:
100000 89731 79663 351984 79663 48602 135355 79663 1628 661293 37635 79663 426439 42597 79663 617809 80941 79663 434012 79663 55353 351562 70259 79663 728593 56083 79663 465864 79663 49873 535094 79663 82032 99951 79663 72331 884689 4287 79663 744479 53983 79663 394859 79663 11490 97473 23469 79663 ...
output:
1 1 0 5 3 2 5 3 9 4 12 9 8 13 7 7 5 8 16 5 9 14 11 6 9 7 9 9 17 10 18 22 10 20 18 31 8 23 34 23 27 15 10 25 42 12 10 30 12 29 37 22 14 12 15 20 17 21 17 46 50 46 25 13 17 15 25 21 46 33 48 52 15 31 13 54 47 51 41 27 13 17 36 13 17 28 42 13 54 16 55 20 43 52 40 20 19 28 34 60 52 20 41 36 40 48 56 38 ...
result:
ok 50000 lines
Test #16:
score: 0
Accepted
time: 162ms
memory: 36428kb
input:
100000 21181 45480 383856 34048 21181 325232 21181 11533 106623 38797 21181 537777 14756 21181 106703 21181 95747 645967 21181 31947 917286 21181 83178 496425 21181 40900 130293 73538 21181 904098 21181 80057 191948 83460 21181 805492 21181 24716 460337 21181 27955 783121 21181 26269 144971 70919 21...
output:
1 1 1 1 3 4 5 7 7 7 7 7 7 10 10 10 10 16 18 18 18 18 19 19 20 20 20 20 20 22 26 26 31 31 34 35 34 34 34 36 36 37 38 39 40 41 43 43 46 46 47 48 49 50 49 53 52 55 55 55 55 55 57 60 58 58 58 62 62 62 61 66 68 67 68 69 68 70 72 73 77 73 76 74 79 78 80 81 81 82 83 84 87 87 89 89 89 89 89 89 91 90 92 94 9...
result:
ok 50000 lines
Test #17:
score: 0
Accepted
time: 1ms
memory: 10776kb
input:
10 10 4 0 7 3 0 10 6 1 5 1 1 5 10 1 8 6 0 10 2 1 1 9 1 1 7 1 10 ? 4 + 6 2 + 9 0 ? 8 + 8 1 + 10 0 ? 4 + 4 2 ? 5 ? 7
output:
0 0 0 2 2
result:
ok 5 lines
Test #18:
score: 0
Accepted
time: 659ms
memory: 68344kb
input:
100000 50403 23870 1 2269 77786 0 88236 65765 0 28248 4408 0 74558 79109 1 75664 73208 1 10792 28375 1 98567 27634 0 90845 81177 0 32096 76545 1 11733 25888 1 68554 31308 0 1066 2492 0 93224 8314 1 69887 89588 1 16083 47361 1 60248 97232 1 86630 50173 0 31340 46107 0 20258 51269 0 39376 44028 0 8841...
output:
0 0 0 0 0 1 0 3 1 3 1 1 1 0 0 0 0 0 1 2 3 5 5 4 9 6 8 0 5 9 0 6 7 7 0 2 7 7 5 10 0 0 0 8 5 7 16 13 2 4 7 3 4 1 1 10 18 2 8 18 1 15 5 13 16 3 11 0 6 13 21 6 0 6 5 16 6 5 1 1 6 24 0 3 20 9 16 4 24 5 14 15 0 0 8 8 11 0 20 10 0 8 7 10 6 8 5 35 2 6 22 1 7 8 3 2 7 4 8 0 8 10 1 13 5 2 4 7 12 36 3 10 2 1 38...
result:
ok 50000 lines
Test #19:
score: 0
Accepted
time: 723ms
memory: 69656kb
input:
100000 49730 265 0 78809 9153 1 65275 81703 0 50422 28990 1 72969 40778 0 21604 34831 0 59452 1530 0 98737 82518 1 37741 5473 1 13736 17478 0 25982 68500 1 86711 84227 0 54130 17469 0 65309 37081 0 35584 46216 1 4853 59899 1 49822 85278 1 8445 72686 0 59147 22165 1 73035 65850 0 16437 25280 0 29017 ...
output:
0 1 1 2 3 4 5 5 10 11 11 12 12 15 16 17 20 21 22 22 22 23 23 24 25 25 26 28 26 28 28 29 29 29 29 31 32 33 34 38 38 38 38 41 41 41 41 43 43 43 44 44 45 45 45 45 45 45 48 48 50 56 56 56 57 57 60 63 63 66 67 68 67 67 67 72 72 72 72 73 73 74 75 77 79 82 82 82 82 83 83 83 84 84 86 87 88 89 89 89 89 89 89...
result:
ok 50000 lines
Test #20:
score: 0
Accepted
time: 656ms
memory: 68664kb
input:
100000 41258 62882 0 64868 74025 1 5722 19530 1 14796 1252 0 2193 72766 0 12881 43335 1 33209 41103 0 35704 53796 0 67373 87901 0 29628 65583 1 30449 73872 0 59461 97707 1 18695 10840 1 92554 59053 1 57943 91567 0 53267 47642 1 41900 45739 0 34663 52104 0 73490 62510 0 31199 75399 1 89391 16176 1 15...
output:
49582 49377 49616 49360 49414 49523 49574 49515 49518 49675 49575 49418 49488 49169 49359 49515 49515 49619 49514 49418 49573 49451 49516 49390 49515 49582 49520 49582 49620 49331 49616 49601 49238 49383 49480 49547 49573 49412 49434 49471 49222 49501 49539 49514 49514 49404 49455 49515 49680 49657 ...
result:
ok 50000 lines
Test #21:
score: 0
Accepted
time: 5ms
memory: 10776kb
input:
10 10 2 81 9 6 39 1 6 85 7 9 31 9 3 99 9 5 71 7 8 91 4 9 72 5 10 15 10 + 8 167 ? 5 ? 9 + 3 61 + 5 239 ? 1 + 3 157 + 6 247 ? 6 ? 9
output:
0 0 1 2 2
result:
ok 5 lines
Test #22:
score: 0
Accepted
time: 722ms
memory: 67612kb
input:
100000 33416 72400 76 8810 46018 53 95687 39082 5 54088 16213 60 12596 96485 53 33591 76915 28 86310 6156 80 23776 4482 31 53780 58274 11 16040 62125 13 98537 85883 54 81308 3654 55 30235 20146 96 49716 61880 26 48285 79037 35 8521 48481 15 75112 63257 49 60693 5439 28 66775 33657 69 10262 64007 3 3...
output:
1 5 8 9 10 12 12 12 12 12 12 13 13 13 13 14 14 15 15 19 19 19 20 23 23 24 26 25 25 26 29 30 30 31 32 33 36 38 38 40 40 40 41 42 43 46 46 46 50 51 52 51 52 54 54 54 54 57 56 58 60 60 60 61 62 61 63 64 64 67 67 68 72 72 71 73 74 76 75 79 79 81 81 81 81 83 85 83 81 85 83 86 85 84 86 87 87 89 88 86 92 9...
result:
ok 50000 lines
Test #23:
score: 0
Accepted
time: 764ms
memory: 70120kb
input:
100000 77041 19377 18 97744 17616 36 37860 32974 94 42455 71716 21 27458 30336 73 99486 65469 87 64427 17284 83 28704 96602 34 41036 61624 7 45693 45912 85 51979 49553 95 99543 7021 74 24055 32520 97 12339 70810 57 27835 77595 41 47527 49193 67 35004 99001 31 11 88065 84 42722 19293 81 97216 27174 9...
output:
2 3 6 6 6 6 6 6 6 8 8 8 10 10 10 13 14 16 17 18 19 20 20 20 20 23 24 24 24 26 27 27 27 28 28 28 32 32 34 34 35 35 35 35 35 36 36 36 41 41 41 41 41 41 41 42 42 42 42 42 44 45 45 45 45 47 49 49 49 52 52 53 55 57 60 60 61 61 64 64 66 67 68 69 70 70 70 71 71 75 76 77 82 82 83 83 83 84 84 84 84 85 87 87 ...
result:
ok 50000 lines
Test #24:
score: 0
Accepted
time: 677ms
memory: 68080kb
input:
100000 67832 80824 45 57521 11588 3 73893 20303 89 99243 98124 35 28565 32549 48 92669 41118 87 40495 44528 22 78924 44280 6 79988 76789 22 55691 15711 75 91688 75476 11 5712 34840 50 46462 46471 55 77521 45788 51 68055 93814 25 36090 33652 72 78695 16093 48 52374 18265 32 61073 63876 2 99193 69139 ...
output:
49955 49934 49947 49942 49934 49937 49901 49937 49929 49960 49935 49936 49949 49945 49917 49945 49917 49949 49954 49920 49937 49916 49936 49940 49928 49945 49918 49929 49949 49922 49940 49923 49928 49913 49921 49939 49939 49939 49934 49929 49947 49936 49935 49920 49910 49948 49917 49945 49937 49914 ...
result:
ok 50000 lines