QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#18787#387. 分身术Qingyu✨100 ✓1406ms75972kbC++2010.1kb2022-01-26 23:10:232022-06-28 16:05:09

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-06-28 16:05:09]
  • Judged
  • Verdict: 100
  • Time: 1406ms
  • Memory: 75972kb
  • [2022-01-26 23:10:23]
  • Submitted

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