QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#18787 | #387. 分身术 | Qingyu✨ | 100 ✓ | 1406ms | 75972kb | C++20 | 10.1kb | 2022-01-26 23:10:23 | 2022-06-28 16:05:09 |
Judging History
answer
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define CLOCKWISE 1
#define ANTICLOCKWISE -1
#define LEFT_CONVEX 1
#define RIGHT_CONVEX -1
#define CONSTRUCT_LAYERS 1
#define SINGLE_QUERY -1
#define MAX_N 100000
#define MAX_LAYERS 100
#define INF (~0U>>1)
using namespace std;
struct Point {
int x, y;
int layer, pos;
int idx;
};
long long cx(Point *a, Point *b, Point *c) {
return (long long) (b->x-a->x)*(c->y-a->y) - (long long) (b->y-a->y)*(c->x-a->x);
}
long long dj(Point *a, Point *b, Point *c) {
return (long long) (b->x-a->x)*(c->x-a->x) + (long long) (b->y-a->y)*(c->y-a->y);
}
struct Hull {
Point **p;
int n;
Hull (int n) {
p = (Point **) malloc(sizeof(Point *) * (n+2));
this->n = n;
}
Point *pos(int x) { while (x <= 0) x += n; while (x >= n) x -= n; return p[x]; }
};
struct Convex {
Point **p;
int h, t;
int sign;
bool refine(Point *a) { bool dom = false; while (h < t && cx(p[t-1], p[t], a) * sign >= 0) --t, dom = true; return dom; }
void push(Point *a) { refine(a); p[++t] = a; }
Point *peek() { return h == t ? NULL : p[h+1]; }
Point *pop() { return p[++h]; }
Point *top() { return p[t]; }
};
struct Opening {
Point *a, *b;
int apos, bpos;
Convex *a_con, *b_con;
};
struct Segment {
int l, r;
};
long long *v[MAX_LAYERS+10];
long long area;
int removed[MAX_N+10];
int idx[MAX_N+10];
Point *o;
Point *p[MAX_N+10], *p2[MAX_N+10], *q[MAX_N+10], *rp[MAX_N+10];
Point **point_heap;
int p_point_heap;
Hull *layer[MAX_LAYERS+10];
Opening *opening[MAX_LAYERS+10];
Opening **s_op, **t_op, **n_op;
Opening *open;
Convex *convex[MAX_LAYERS+10];
int n_convex;
Segment segment[MAX_LAYERS+10];
bool cmp_pointrp(Point *a, Point *b) {
return a->layer == b->layer ? a->pos < b->pos : a->layer < b->layer;
}
bool cmp_point2d(Point *a, Point *b) {
return a->x == b->x ? a->y < b->y : a->x < b->x;
}
bool cmp_opening(Opening *a, Opening *b) {
return a->apos < b->apos;
}
void init() {
o = new Point();
o->x = o->y = 0;
point_heap = (Point **) malloc(sizeof(Point*) * (4 * MAX_LAYERS * MAX_LAYERS));
open = new Opening();
open->apos = -INF;
open->bpos = INF;
}
void clear_for_query() {
opening[0] = open;
s_op = n_op = opening;
t_op = s_op+1;
p_point_heap = 0;
area = v[1][0];
}
Point **point_malloc(int n) {
Point **p = point_heap + (p_point_heap);
p_point_heap += n;
return p;
}
Convex *new_convex(int sign, Point *a) {
Convex *con = new Convex();
con->p = point_malloc(MAX_LAYERS+2);
con->h = 1, con->t = 0;
con->sign = sign;
con->push(a);
return con;
}
Opening *new_opening(Point *a, Point *b, Point *pa, Point *pb, Convex *a_con, Convex *b_con) {
Opening *op = new Opening();
op->a = a, op->b = b;
op->apos = pa->pos, op->bpos = pb->pos;
op->a_con = a_con;
op->b_con = b_con;
if (op->apos > op->bpos)
op->bpos += layer[pa->layer]->n;
return op;
}
long long cxsum(Point *a, Point *b) {
long long *vp = v[a->layer];
return a->pos <= b->pos ? vp[b->pos]-vp[a->pos] : vp[0] - (vp[a->pos]-vp[b->pos]);
}
Point *find_tangle(Hull *hull, Point *a, int sign) {
int n = hull->n;
int bias = sign == -1;
if (n == 0)
return NULL;
if (n == 1)
return hull->p[n];
Point *b = hull->pos(sign+bias);
bool dom = cx(a, hull->pos(sign+bias), hull->pos(bias)) * sign <= 0;
int l = 2, r = n, j, an = 1;
for (; j = (l+r)>>1, l <= r; ) {
if (cx(a, b, hull->pos(sign*j+bias)) * sign <= 0) {
if (dom) r = j-1;
else l = j+1;
}
else if (cx(a, hull->pos(sign*j+bias), hull->pos(sign*(j-1)+bias)) * sign <= 0)
an = j, l = j+1;
else r = j-1;
} return hull->pos(sign*an+bias);
}
bool find_new_opening(Hull *hull, Point *a, Point *b, Convex *a_con, Convex *b_con) {
Point *s1 = a, *s2 = b;
Point *pa, *pb;
while (a->idx != b->idx) {
pa = find_tangle(hull, a, CLOCKWISE);
pb = find_tangle(hull, b, ANTICLOCKWISE);
if (a_con->peek() && (pa == NULL || cx(a, pa, a_con->peek()) >= 0)) {
area += cx(o, a, a_con->peek());
a = a_con->pop();
}
else if (b_con->peek() && (pb == NULL || cx(b, b_con->peek(), pb) >= 0)) {
area += cx(o, b_con->peek(), b);
b = b_con->pop();
}
else {
area += cx(o, a, pa) + cx(o, pb, b) + cxsum(pa, pb);
*(++n_op) = new_opening(a, b, pa, pb, a_con, b_con);
return 1;
}
}
return 0;
}
void layer_by_layer(int m, Point **rp) {
Point *a, *b, *ia, *ib, *a_del, *b_del;
Convex *a_con, *b_con;
Segment *seg_s, *seg, *seg_end;
Hull *cur, *hull;
sort(rp+1, rp+m+1, cmp_pointrp);
int s = 1, t;
int num = 0;
Point *record = NULL;
Point *pa, *pb;
for (int i = 1; i <= MAX_LAYERS; ++i, s = t) {
cur = layer[i], hull = layer[i+1];
if (num == 1) {
pa = find_tangle(cur, record, CLOCKWISE);
pb = find_tangle(cur, record, ANTICLOCKWISE);
*s_op = new_opening(record, record, pa, pb, new_convex(LEFT_CONVEX, record), new_convex(RIGHT_CONVEX, record));
area = cxsum(pa, pb) + cx(o, record, pa) + cx(o, pb, record);
}
if (s > m || rp[s]->layer != i)
break;
t = s;
while (t <= m && rp[t]->layer == rp[s]->layer)
++t;
if (t == s) {
break;
}
if (cur->n - (t-s) == 1 && num == 0) {
num = 1;
for (int j = 0; j < cur->n; ++j)
if (removed[cur->p[j]->idx] == false) {
record = cur->p[j];
break;
}
continue;
}
if (cur->n - (t-s) == 0 && num == 0) {
area = v[i+1][0];
continue;
}
if (t - s == cur->n) {
if (num == 1)
continue;
for (Opening **p_op = s_op; p_op != t_op; ++p_op) {
Opening *op = *p_op;
area -= cx(o, op->a, cur->pos(op->apos));
area -= cx(o, cur->pos(op->bpos), op->b);
area -= cxsum(cur->pos(op->apos), cur->pos(op->bpos));
find_new_opening(hull, op->a, op->b, op->a_con, op->b_con);
}
s_op = t_op;
t_op = n_op + 1;
sort(s_op, t_op, cmp_opening);
continue;
}
seg_s = seg = segment;
for (int j = s+1; j < t; ++j)
if (rp[j]->pos != rp[j-1]->pos+1) {
seg->r = rp[j-1]->pos;
(++seg)->l = rp[j]->pos;
}
if (rp[s]->pos == 1 && rp[t-1]->pos == cur->n) {
seg_s->l = seg->l - cur->n;
--seg;
}
else seg_s->l = rp[s]->pos, seg->r = rp[t-1]->pos;
int n_seg = seg-seg_s+1;
while (seg->r < 2*cur->n) {
++seg;
seg->r = (seg-n_seg)->r + cur->n;
seg->l = (seg-n_seg)->l + cur->n;
}
if (num <= 0) seg_end = seg_s + n_seg;
else seg_end = seg+1;
seg = seg_s;
for (Opening **p_op = s_op; p_op != t_op; ++p_op) {
Opening *op = *p_op;
while (seg != seg_end && seg->r < op->apos)
++seg;
while (seg != seg_end && seg->l <= op->bpos) {
ia = cur->pos(seg->l-1);
ib = cur->pos(seg->r+1);
if (seg->l <= op->apos) {
a = op->a, a_con = op->a_con;
a_del = cur->pos(op->apos);
area -= cx(o, a, a_del);
}
else {
a = ia, a_con = new_convex(LEFT_CONVEX, a);
a_del = ia;
}
if (seg->r >= op->bpos) {
b = op->b, b_con = op->b_con;
b_del = cur->pos(op->bpos);
area -= cx(o, b_del, b);
}
else {
b = ib, b_con = new_convex(RIGHT_CONVEX, b);
b_del = ib;
}
if (b == ib) {
while (a_con->h < a_con->t && cx(a, b, a_con->top()) <= 0) --a_con->t;
a_con->push(b);
}
else if (a == ia) {
while (b_con->h < b_con->t && cx(a, b, b_con->top()) <= 0) --b_con->t;
b_con->push(a);
}
if (cx(a, b, ia) > 0 && (a_con->refine(ia) || b_con->refine(ia)))
a_con->push(ia), b_con->push(ia);
if (cx(a, b, ib) > 0 && (a_con->refine(ib) || b_con->refine(ib)))
b_con->push(ib), a_con->push(ib);
area -= cxsum(a_del, b_del);
find_new_opening(hull, a, b, a_con, b_con);
if (seg->r >= op->bpos)
break;
++seg;
}
}
num += cur->n - (t-s);
s_op = t_op;
t_op = n_op + 1;
sort(s_op, t_op, cmp_opening);
}
}
void bruteforce(int n, Point **p, int &t, Point **q, int mode) {
int h;
h = 1, t = 0;
for (int i = 1; i <= n; ++i) {
if (mode == CONSTRUCT_LAYERS && p[i]->layer != 0)
continue;
if (mode == SINGLE_QUERY && removed[p[i]->idx] == true)
continue;
while (t > 1 && cx(q[t-1], q[t], p[i]) >= 0) --t;
q[++t] = p[i];
}
h = t, --t;
for (int i = n; i >= 1; --i) {
if (mode == CONSTRUCT_LAYERS && p[i]->layer != 0)
continue;
if (mode == SINGLE_QUERY && removed[p[i]->idx] == true)
continue;
while (h < t && cx(q[t-1], q[t], p[i]) >= 0) --t;
q[++t] = p[i];
}
if (t == 1) t = 2, q[t+1] = q[1];
if (t <= 0) t = 1;
}
void construct_layers(int n, Point **p, Point **q) {
int t;
sort(p+1, p+n+1, cmp_point2d);
for (int i = 1; i <= MAX_LAYERS+1; ++i) {
bruteforce(n, p, t, q, CONSTRUCT_LAYERS);
Hull *hull = new Hull(t-1);
layer[i] = hull;
if (t == 1)
break;
for (int j = 1; j < t; ++j) {
q[j]->layer = i;
q[j]->pos = j;
hull->p[j] = q[j];
}
hull->p[0] = hull->p[t-1];
hull->p[t] = hull->p[1];
long long *vp = (long long *) malloc(sizeof(long long)*(t+2));
for (int j = 1; j <= t; ++j)
vp[j] = j == 1 ? 0 : vp[j-1] + cx(o, q[j-1], q[j]);
vp[0] = vp[t];
v[i] = vp;
}
}
int main() {
init();
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
int x, y;
Point *pt = new Point();
scanf("%d %d", &x, &y);
pt->x = x, pt->y = y;
pt->idx = i;
p[i] = p2[i] = pt;
}
construct_layers(n, p2, q);
for (int i = 1; i <= m; ++i) {
int rc = i == 1 ? (n-1) : (-area) % n;
clear_for_query();
int x, k, t = 0;
scanf("%d", &k);
for (int j = 1; j <= k; ++j) {
scanf("%d", idx+j);
idx[j] = (idx[j] + 1LL*rc) % n + 1;
if (removed[idx[j]] == true)
continue;
removed[idx[j]] = true;
if (p[idx[j]]->layer != 0)
rp[++t] = p[idx[j]];
}
layer_by_layer(t, rp);
for (int j = 1; j <= k; ++j)
removed[idx[j]] = false;
cout << -area << endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 5
Accepted
time: 3ms
memory: 5816kb
input:
10 10 2 5 2 6 6 5 5 1 3 6 7 0 6 2 5 2 2 4 3 4 4 5 3 2 7 3 4 5 3 2 1 8 3 0 8 9 4 8 9 2 1 4 1 0 8 9 2 6 8 4 0 7 3 6 4 6 7 9 5 4 5 4 1 8
output:
8 17 24 14 10 22 28 19 20 19
result:
ok 10 lines
Test #2:
score: 5
Accepted
time: 17ms
memory: 6468kb
input:
1000 1000 92387951 -38268342 96962025 2625381 68101265 31039140 0 97151898 26143938 -93117014 -84810126 11065278 0 90189873 40082738 -87677340 66075949 27805594 6356978 -98680389 66385050 -73600998 -68181818 -63636363 29782405 -91901062 86835443 12566968 -60506329 29068478 0 98734177 -27594936 39273...
output:
54005531591726153 53840025650740922 53784548444158833 53965534948392825 52310978083346044 54015775343604808 53878160541021326 53793056185243309 53978269716445514 53969402703417552 53965534948392825 53776770495489199 53859093126007706 54011681370414937 50267813614927260 53980117308108098 538018907002...
result:
ok 1000 lines
Test #3:
score: 5
Accepted
time: 9ms
memory: 6556kb
input:
1000 1000 98502865 -6879029 38564813 -88341751 43898266 -85979753 0 85126582 40902054 -87635172 65063291 30057008 39643536 -88015634 91392405 6366511 0 60759493 48860759 40274859 97915651 -9293492 58481012 38451175 85681319 -44005128 0 62658227 -54430379 43486260 84802899 -45880284 98310526 -7684674...
output:
53721752778173237 53768219734173877 53936127654621019 51918909564226578 53884857342747315 53837920094757117 53861153499339717 53791453138756477 53751861403465850 51521737422695250 53958916931053800 53791453138756477 53956327583523250 53733966788056510 53913880840644495 53837920094757117 537636249228...
result:
ok 1000 lines
Test #4:
score: 5
Accepted
time: 10ms
memory: 6468kb
input:
1000 1000 36881226 -89039117 0 68987341 0 69620253 87341772 10352380 46480700 -84941593 95019482 -19663022 0 80696202 -50000000 -40909090 98310526 -7684674 45316455 44374065 -40759493 38298521 91702167 -29469516 22025316 60144908 53924050 24408021 89152890 -36031806 58399172 -78488044 -59090909 -636...
output:
53914957018376775 54171394381987149 54272068976647324 54275436415417361 54444402103815662 53365190531581950 54320282996342051 54250627919244031 52784578362171023 54215812624404861 54192224396920653 54215812624404861 54241930176123336 54268047810373456 54464885576819664 54245924875600628 544566817045...
result:
ok 1000 lines
Test #5:
score: 5
Accepted
time: 465ms
memory: 15096kb
input:
50000 100000 -12384687 99230134 -41227667 7399055 -18961769 -98185799 -83825736 54527478 98039809 19686160 79981944 -60018644 89428570 44742373 2849412 99956140 -4397163 -99903277 69954343 71454454 -58497556 81105091 -77834932 62783144 84150928 -54018241 -14287837 83296400 2596190 99963038 99870667 ...
output:
62830572879051045 62830572879043021 62830572879052917 62830572879075861 62830572879059096 62830572879026115 62830572879050957 62830572879007669 62830572879024107 62830572879035238 62830572879043201 62830572879045462 62830572879050254 62830572879029194 62830572879045546 62830572879012454 628305728790...
result:
ok 100000 lines
Test #6:
score: 5
Accepted
time: 597ms
memory: 14156kb
input:
60000 100000 -38285737 -29615111 -28007361 60117512 68300807 73036626 60899595 79313230 98653797 -16333324 94366720 -33079770 91071768 -41295061 -31139804 52937241 -39334272 24206618 95131180 -30812461 -40932098 -11753446 89887464 43813159 -2970190 96938845 -9970871 88917981 -50455806 -86337776 9523...
output:
62830572982312709 62830572982320247 62830572982349410 62830572982331600 62830572982332136 62830572982332198 62830572982362271 62830572982341940 62830572982359327 62830572982338608 62830572982339559 62830572982341769 62830572982339215 62830572982341116 62830572982338654 62830572982338253 628305729823...
result:
ok 100000 lines
Test #7:
score: 5
Accepted
time: 526ms
memory: 15644kb
input:
60000 100000 94957552 31343459 -23732842 -97142947 -4041351 -99918304 474336 -99995620 98448554 17528013 98083938 -19465103 35500650 93482902 41251856 91091347 34958074 93687150 -86427468 50302014 -40923444 -11856759 45205401 89195408 91097868 -41237453 49667857 86789706 -2092946 -97862302 83398488 ...
output:
62830572982320964 62830572982335108 62830572982320226 62830572982326434 62830568866130098 62830572982319038 62830572982342324 62830572982321660 62830572982321396 62830572982318247 62830572982331224 62830572982340968 62830572982332414 62830572982299250 62830572982362250 62830572982320275 628305729823...
result:
ok 100000 lines
Test #8:
score: 5
Accepted
time: 599ms
memory: 15828kb
input:
70000 100000 -25468154 65251376 -41366073 -3953876 -30578817 95209956 76749702 64100174 -1018066 -98971461 99923686 -3821788 92315276 -38434865 69668476 71733204 88445239 46656068 -32189493 50258709 -9607955 99537365 -94229489 33478399 -92200501 38717793 -23591716 -68739271 -61972290 78482069 -82254...
output:
62830573041129653 62830573041133886 62830573041095862 62830573041139396 62830573041105574 62830573041107134 62830573041095789 62830573041098296 62830573041119842 62830573041115508 62830573041096074 62830573041105037 62830573041106296 62830573041129955 62830573041113673 62830573041119059 628305730410...
result:
ok 100000 lines
Test #9:
score: 5
Accepted
time: 511ms
memory: 20152kb
input:
50000 100000 27081161 -96263128 -83993170 -54269114 78388843 -62090002 -34538786 -93845891 -94463020 -32813520 -20905171 -97790404 -4666971 -99890933 -32923672 -94424631 -68100276 -73227942 99683049 -7954167 4073645 -99916888 2446819 -99969956 53747810 -84327646 46051878 -88764878 98823944 -15291435...
output:
49222770401247195 51415925123172156 47667214820136084 47667214820136084 47667214820136084 51415925122389163 51415925123193970 47667214820136084 47667214820136084 47667214820136084 51415925123228864 47667214820136084 51415925123132921 49222770401247195 47667214820136084 49222770401247195 492227704012...
result:
ok 100000 lines
Test #10:
score: 5
Accepted
time: 610ms
memory: 22020kb
input:
60000 100000 -55128563 -83431595 -95957175 -28146043 -13872619 -99032973 -31730304 -94832364 16074629 -98699471 2543096 -99967555 -34545773 -93843321 -78932039 -61397984 99856192 -5359131 55294253 -83321815 73226732 -68101653 65847328 -75260272 29344296 -95597550 95048852 -31075966 67031025 -7420809...
output:
49002626510934812 51415925432658457 51415925432218368 47891515388712590 51415925432664155 51415925432703977 49002626510934812 47891515388712590 47891515388712590 51415925432680767 47891515388712590 49002626510934812 51415925432699288 51415925432192184 51415925432174078 51415925432667961 514159254326...
result:
ok 100000 lines
Test #11:
score: 5
Accepted
time: 471ms
memory: 23064kb
input:
50000 100000 241596 -99999542 -59624690 -80279904 -97212774 -23444470 97890224 -20432100 -86335021 -50460191 -87958444 -47573929 97827746 -20729677 -99626940 -8627829 95199058 -30612355 -37923677 -92529786 55347336 -83286549 95302724 -30287909 -65022404 -75974033 -99819259 -6006846 -10194157 -994788...
output:
47645213463610886 49017579683610886 51415921475380637 47645213463610886 47645213463610886 51415921458535421 51415921458531289 51415921458350950 47645213463610886 51415921466966466 49017579683610886 51415921475247536 49017579683610886 51415921475298077 51415921466864105 51415921475196668 476452134636...
result:
ok 100000 lines
Test #12:
score: 5
Accepted
time: 613ms
memory: 35056kb
input:
53000 100000 -44787673 -89409106 90736108 -42034054 -75406065 -65679899 -11770656 -99304354 16345925 -98654569 -91440284 -40479987 29216305 -95636399 98327268 -18211302 -29770116 -95465404 -34714447 -93780650 -55523983 -83168507 -88335387 -46869633 96824561 -24998352 -1735429 -99984456 73724383 -675...
output:
51415852955942693 51415852460849995 48371781329819440 49841489305316044 49841489305316044 48927336857597218 48927336857597218 48371781329819440 48927336857597218 47816225735374996 51415852466750091 48371781329819440 51415852592077571 48807870957538266 51415852704398338 51415852710319380 514158524832...
result:
ok 100000 lines
Test #13:
score: 5
Accepted
time: 681ms
memory: 40108kb
input:
56000 100000 53969497 -80769645 60097403 -77345515 3344351 -99308494 65732628 -73938776 65517805 -74073053 22443105 -94182036 38640981 -88122822 55827926 -79759938 18433058 -95444519 47562922 -84057555 87626034 -39658251 86109347 -43072321 60218231 -77275739 63928630 -75057626 97309601 -11655878 990...
output:
54591734024387113 54484464329605691 54591734024387113 54591734024387113 54480553403783133 54488626629354950 54578798024387113 54591734024387113 54500002744105466 54496116241880757 54591734024387113 54486037447334930 54540142050064664 54591734024387113 54518129892405147 54342918802382962 545239555267...
result:
ok 100000 lines
Test #14:
score: 5
Accepted
time: 820ms
memory: 41620kb
input:
60000 100000 96284797 -15398996 80783776 -53868197 7214023 -98437807 45006550 -85271926 44555263 -85531907 76043857 -62271774 98965408 -4876539 79732222 -55817974 33042127 -90408657 26718647 -92765200 7538031 -98356616 69029693 -71824371 70183312 -71063306 35853023 -89288719 73291688 -66745210 59161...
output:
54146498173620005 54335582053473554 54372854616447928 54149610901510487 54435089874621907 54424951631821907 54182105562952303 54333811886322085 54424951631821907 54156210349796036 54429432525741907 54182106825848403 54198291711259645 54429432525741907 54357316164689676 54363144748576420 544294325257...
result:
ok 100000 lines
Test #15:
score: 5
Accepted
time: 1104ms
memory: 56832kb
input:
100000 100000 52110252 -81805175 42437475 -86452608 78709543 -57665157 72851236 -67436908 17527185 -95697274 36825607 -88904663 81674124 -52174916 93159774 -25368366 25016993 -93322509 26138767 -92974539 13094552 -96945754 51934709 -81903125 52229203 -81685056 78766835 -57562906 90616943 -32348920 7...
output:
54258326075792105 54252636823312105 53989686593124344 54140680628283973 54216098403472105 53948366533446366 54231434403472105 54228878403472105 54236546403472105 54241658403472105 54228878403472105 54252636823312105 54226322403472105 54274314787049437 53970063939706562 54233990403472105 541376453762...
result:
ok 100000 lines
Test #16:
score: 5
Accepted
time: 1354ms
memory: 72500kb
input:
80000 100000 0 77350000 18523125 -95403262 13148872 -96931287 68055106 -72462630 75834536 -62621616 6852412 -98524937 49884113 -82888751 40459113 -87331513 97722103 -10061320 33183598 -90347987 57514313 -78851693 49137043 -83265560 84256008 -47022340 49127890 -83310965 35988482 -89227102 90720932 -3...
output:
54536146506033461 54313526666202378 54594850053875055 54541974172361598 52414212727792294 50904734257327058 50896802712017802 54515038321381117 54591837487875055 54340476881590801 54553718353935039 50916877736233505 51147533799959958 54607522053875055 54530412290801675 54591837487875055 546163021237...
result:
ok 100000 lines
Test #17:
score: 5
Accepted
time: 1406ms
memory: 75496kb
input:
85000 100000 59354059 -77775593 94844093 -20227388 30856014 -91243866 72082820 -68628591 45391661 -85086660 22765111 -94090041 74442550 -64907104 38907648 -88004888 27259080 -92548597 48826930 -83418569 83371931 -48829606 25183996 -93266437 80910853 -53628956 20461778 -94853539 95614182 -17702962 89...
output:
54644635485620569 54567582121574240 53203117398125819 52429499918579114 54665966189220569 54372371170226047 54601491631217307 54560622190147066 54665966189220569 54578181784037908 52764127335778751 54562242405397122 54400353780848964 54577273039725237 52912798392806741 54374894628827886 545911336559...
result:
ok 100000 lines
Test #18:
score: 5
Accepted
time: 1372ms
memory: 72712kb
input:
90000 100000 40851366 -87160949 85920616 -43485213 78152934 -58651188 30278435 -91452381 79163488 -56851018 524405 -99895835 30994217 -91189836 45340073 -85112319 83191746 -49192271 99980094 -99928 15632958 -96244087 58178312 -78447123 88016623 -38749698 88069632 -38625412 94342805 -21808388 3991800...
output:
53046337208006179 53241616936364316 53329751722418373 53322059722418373 53304111722418373 53332315722418373 53324623722418373 51498390834830097 53214723114286035 53316931722418373 53059934814805797 53316931722418373 53319495722418373 53314367722418373 53028698611305362 53327187722418373 524158935828...
result:
ok 100000 lines
Test #19:
score: 5
Accepted
time: 1404ms
memory: 74340kb
input:
95000 100000 8598078 -98100812 16368192 -96037622 44975999 -85293696 16100539 -96110912 39132186 -87909214 75217456 -63643465 98319692 -7646619 73842281 -65871462 99274998 -3479747 91900508 -28928032 96473182 -14732237 53422265 -81073354 92608216 -26954407 74023288 -65581975 65875155 -73851173 80226...
output:
53834120869201111 52238523625155827 54101301242936736 54015907487759468 53840466840683716 54117442680536736 53859891001070276 54109389242936736 53850178984069930 53818574584707637 54046758114325708 54106693242936736 54109389242936736 53828170030445541 54101301242936736 54015539047541001 540254044177...
result:
ok 100000 lines
Test #20:
score: 5
Accepted
time: 1362ms
memory: 75972kb
input:
100000 100000 97263300 -11831478 75786964 -62700895 12186736 -97189474 90934040 -31521604 74311316 -65119003 45011394 -85262180 27104912 -92600526 15627609 -96246344 88465873 -37688772 8169756 -98203882 9128373 -97970945 61464490 -76540188 86137636 -43010213 81609046 -52300051 7729916 -98310189 9606...
output:
53418745009606770 54437329485674333 54420182615194333 54424982615194333 54424982615194333 54433601485674333 54422582615194333 53203446188369907 54422582615194333 54326988753447813 53439020993399759 54329349549234769 54429873485674333 54422582615194333 54130458667873922 54339061877704675 544373294856...
result:
ok 100000 lines
Extra Test:
score: 0
Extra Test Passed