QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#616688#1838. Intellectual ImplementationlopgovAC ✓1100ms158944kbC++1410.3kb2024-10-06 10:15:392024-10-06 10:15:40

Judging History

你现在查看的是最新测评结果

  • [2024-10-06 10:15:40]
  • 评测
  • 测评结果:AC
  • 用时:1100ms
  • 内存:158944kb
  • [2024-10-06 10:15:39]
  • 提交

answer

# include <bits/stdc++.h>
using namespace std;
// typedef long long ll;
typedef unsigned long long ull;
// # define int long long
#define int __int128_t
#define ll __int128_t
# define lc u << 1
# define rc u << 1 | 1
# define fi first
# define se second
const int N = 4e5 + 5;

namespace IO
{
	const int N = 1e6 + 5;
	char obuf[N], * p3 = obuf; char ibuf[N], * p1 = ibuf, * p2 = ibuf;
	inline void flush() { fwrite(obuf, p3 - obuf, 1, stdout); p3 = obuf; }
	inline void putch(char x) { (p3 - obuf < N) ? (*p3++ = x) : (flush(), *p3++ = x); }
	inline char getch() { return p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, N, stdin), p1 == p2) ? EOF : *p1++; }
	inline bool READ(char& p) { p = getch(); while (p == ' ' || p == '\n' || p == -1) { if (p == -1) return true; p = getch(); } return false; }
	inline bool READ(char* p) { char ch = getch(); while (ch == ' ' || ch == '\n' || ch == -1) { if (ch == -1) return true; ch = getch(); } while (ch != ' ' && ch != '\n' && ch != -1) { *p++ = ch; ch = getch(); } *p++ = '\0'; return ch == -1; }
	inline bool READ(std::string& str) { str = ""; char ch = getch(); while (ch == ' ' || ch == '\n' || ch == -1) { if (ch == -1) return true; ch = getch(); } while (ch != ' ' && ch != '\n' && ch != -1) { str += ch; ch = getch(); } return ch == -1; }
	inline bool READ(signed& x) { register char ch = getch(); while (ch < '0' || ch > '9') { if (ch == -1) return true; if (ch == '-') { if (READ(x)) { x = -x; return true; } x = -x; return false; } ch = getch(); } x = 0; while (ch <= '9' && ch >= '0') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getch(); } if (ch == -1) return true; return false; } inline bool READ(unsigned& x) { register char ch = getch(); while (ch < '0' || ch > '9') { if (ch == -1) return true; ch = getch(); } x = 0; while (ch <= '9' && ch >= '0') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getch(); } if (ch == -1) return true; return false; }
	inline bool READ(short& x) { register char ch = getch(); while (ch < '0' || ch > '9') { if (ch == -1) return true; if (ch == '-') { if (READ(x)) { x = -x; return true; } x = -x; return false; } ch = getch(); } x = 0; while (ch <= '9' && ch >= '0') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getch(); } if (ch == -1) return true; return false; } inline bool READ(unsigned short& x) { register char ch = getch(); while (ch < '0' || ch > '9') { if (ch == -1) return true; ch = getch(); } x = 0; while (ch <= '9' && ch >= '0') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getch(); } if (ch == -1) return true; return false; }
	inline bool READ(long long& x) { register char ch = getch(); while (ch < '0' || ch > '9') { if (ch == -1) return true; if (ch == '-') { if (READ(x)) { x = -x; return true; } x = -x; return false; } ch = getch(); } x = 0; while (ch <= '9' && ch >= '0') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getch(); } if (ch == -1) return true; return false; } inline bool READ(unsigned long long& x) { register char ch = getch(); while (ch < '0' || ch > '9') { if (ch == -1) return true; ch = getch(); } x = 0; while (ch <= '9' && ch >= '0') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getch(); } if (ch == -1) return true; return false; }
	inline bool READ(__int128_t& x) { register char ch = getch(); while (ch < '0' || ch > '9') { if (ch == -1) return true; if (ch == '-') { if (READ(x)) { x = -x; return true; } x = -x; return false; } ch = getch(); } x = 0; while (ch <= '9' && ch >= '0') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getch(); } if (ch == -1) return true; return false; } inline bool READ(__uint128_t& x) { register char ch = getch(); while (ch < '0' || ch > '9') { if (ch == -1) return true; ch = getch(); } x = 0; while (ch <= '9' && ch >= '0') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getch(); } if (ch == -1) return true; return false; }
	inline bool read() { return false; }
	template < typename T, typename ... T2 > inline bool read(T& x, T2& ... oth) { if (READ(x)) return true; return read(oth...); }
	inline int Read() { register int x = 0; read(x); return x; }
	inline void WRITE(char ch) { putch(ch); }
	inline void WRITE(char* ch) { register int len = strlen(ch); for (register int i = 0; i < len; i++) putch(ch[i]); }
	inline void WRITE(std::string ch) { register int siz = ch.size(); for (register int i = 0; i < siz; i++) putch(ch[i]); }
	inline void WRITE(signed x) { if (!x) { putch('0'); return; } register int len = 0; register signed k1 = x; register char c[50] = {}; if (k1 < 0) k1 = -k1, putch('-'); while (k1) c[len++] = k1 % 10 ^ 48, k1 /= 10; while (len--) putch(c[len]); }
	inline void WRITE(unsigned x) { if (!x) { putch('0'); return; } register int len = 0; register unsigned k1 = x; register char c[50] = {}; while (k1) c[len++] = k1 % 10 ^ 48, k1 /= 10; while (len--) putch(c[len]); }
	inline void WRITE(short x) { if (!x) { putch('0'); return; } register int len = 0; register short k1 = x; register char c[50] = {}; if (k1 < 0) k1 = -k1, putch('-'); while (k1) c[len++] = k1 % 10 ^ 48, k1 /= 10; while (len--) putch(c[len]); }
	inline void WRITE(unsigned short x) { if (!x) { putch('0'); return; } register int len = 0; register unsigned short k1 = x; register char c[50] = {}; while (k1) c[len++] = k1 % 10 ^ 48, k1 /= 10; while (len--) putch(c[len]); }
	inline void WRITE(long long x) { if (!x) { putch('0'); return; } register int len = 0; register long long k1 = x; register char c[50] = {}; if (k1 < 0) k1 = -k1, putch('-'); while (k1) c[len++] = k1 % 10 ^ 48, k1 /= 10; while (len--) putch(c[len]); }
	inline void WRITE(unsigned long long x) { if (!x) { putch('0'); return; } register int len = 0; register unsigned long long k1 = x; register char c[50] = {}; while (k1) c[len++] = k1 % 10 ^ 48, k1 /= 10; while (len--) putch(c[len]); }
	inline void WRITE(__int128_t x) { if (!x) { putch('0'); return; } register int len = 0; register __int128_t k1 = x; register char c[50] = {}; if (k1 < 0) k1 = -k1, putch('-'); while (k1) c[len++] = k1 % 10 ^ 48, k1 /= 10; while (len--) putch(c[len]); }
	inline void WRITE(__uint128_t x) { if (!x) { putch('0'); return; } register int len = 0; register __uint128_t k1 = x; register char c[50] = {}; while (k1) c[len++] = k1 % 10 ^ 48, k1 /= 10; while (len--) putch(c[len]); }
	inline void write() {  }
	template < typename T, typename ... T2 > inline void write(T x, T2 ... oth) { WRITE(x); write(oth...); }
	template < typename T, typename ... T2 > inline void writef(T x, T2 ... oth) { WRITE(x); write(oth...); flush(); }
} using IO::getch; using IO::READ; using IO::WRITE; using IO::read; using IO::write; using IO::writef; using IO::flush; using IO::putch; using IO::getch; using IO::Read;

int n;
struct node
{
	int x1, x2, y1, y2;
	bool operator < (const node &t) const { return y1 < t.y1; }
} a[N];
int tmp[N * 2], tot;
ll deg[N];
struct xian
{
	int x, y1, y2, id, flag;
} line[N * 2];
int lowbit (int x) { return x & (-x); }
struct BIT
{
	int c[N * 2];
	void modify (int x, ll w) { for (; x < N; x += lowbit (x)) c[x] += w; }
	ll query (int x) { int s = 0; for (; x; x -= lowbit (x)) s += c[x]; return s; }
} shangy1, shangy2, xiay1, xiay2, xjy1, xjy2;
struct Segment
{
	struct tree
	{
		ll cntl, cntr, cnt;
		tree operator + (const tree &t) const
		{
			return {cntl + t.cntl, cntr + t.cntr, cnt + t.cnt + cntl * t.cntr};
		}
	} tr[(N * 2) << 2];
	void pushup (int u) { tr[u] = tr[lc] + tr[rc]; }
	void modify (int u, int l, int r, int x, int w, int op)
	{
		if (l == r)
		{
			if (op == 1) tr[u].cntl += w;
			else tr[u].cntr += w;
			return;
		}
		int mid = l + r >> 1;
		if (x <= mid) modify (lc, l, mid, x, w, op);
		else modify (rc, mid + 1, r, x, w, op);
		pushup (u);
	}
	tree query (int u, int l, int r, int x, int y)
	{
		if (x <= l && y >= r) return tr[u];
		int mid = l + r >> 1;
		if (y <= mid) return query (lc, l, mid, x, y);
		if (x > mid) return query (rc, mid + 1, r, x, y);
		return query (lc, l, mid, x, y) + query (rc, mid + 1, r, x, y); 
	}
} seg;
int C (ll n, int m)
{
	if (m == 2) return n * (n - 1) / 2;
	else return n * (n - 1) * (n - 2) / 6;
}
signed main ()
{
//	freopen ("rectangle.in", "r", stdin); freopen ("rectangle.out", "w", stdout);
	// scanf ("%lld", &n);
	read(n);
	// for (int i = 1; i <= n; i ++ ) 
		// scanf ("%lld%lld%lld%lld", &a[i].x1, &a[i].x2, &a[i].y1, &a[i].y2);
	for (int i = 1; i <= n; i++) read(a[i].x1, a[i].x2, a[i].y1, a[i].y2);
	for (int i = 1; i <= n; i ++ ) tmp[ ++ tot] = a[i].x1, tmp[ ++ tot] = a[i].x2;
	sort (tmp + 1, tmp + 1 + tot); tot = unique (tmp + 1, tmp + 1 + tot) - (tmp + 1);
	for (int i = 1; i <= n; i ++ )
	{
		a[i].x1 = lower_bound (tmp + 1, tmp + 1 + tot, a[i].x1) - tmp;
		a[i].x2 = lower_bound (tmp + 1, tmp + 1 + tot, a[i].x2) - tmp;
	}
	tot = 0;
	for (int i = 1; i <= n; i ++ ) tmp[ ++ tot] = a[i].y1, tmp[ ++ tot] = a[i].y2;
	sort (tmp + 1, tmp + 1 + tot); tot = unique (tmp + 1, tmp + 1 + tot) - (tmp + 1);
	for (int i = 1; i <= n; i ++ )
	{
		a[i].y1 = lower_bound (tmp + 1, tmp + 1 + tot, a[i].y1) - tmp;
		a[i].y2 = lower_bound (tmp + 1, tmp + 1 + tot, a[i].y2) - tmp;
	}
	sort (a + 1, a + 1 + n);
	for (int i = 1; i <= n; i ++ )
	{
		line[a[i].x1] = {a[i].x1, a[i].y1, a[i].y2, i, 1};
		line[a[i].x2] = {a[i].x2, a[i].y1, a[i].y2, i, -1};
	}
	ll sum = 0;
	for (int i = 1; i <= n * 2; i ++ )
	{
		int x = line[i].id;
		if (line[i].flag == 1)
		{
			deg[x] += xiay2.query (line[i].y1 - 1) - xiay1.query (line[i].y2);
			sum += C (xjy1.query (line[i].y2) - xjy2.query (line[i].y1 - 1), 2) - seg.query (1, 1, n * 2, line[i].y1, line[i].y2).cnt;
			shangy1.modify (line[i].y1, 1), shangy2.modify (line[i].y2, 1);
			xjy1.modify (line[i].y1, 1), xjy2.modify (line[i].y2, 1);
			seg.modify (1, 1, n * 2, line[i].y2, 1, 1), seg.modify (1, 1, n * 2, line[i].y1, 1, 2);
		}
		else
		{
			deg[x] += shangy1.query (line[i].y2) - shangy2.query (line[i].y1 - 1);
			xiay1.modify (line[i].y1, 1); xiay2.modify (line[i].y2, 1);
			xjy1.modify (line[i].y1, -1); xjy2.modify (line[i].y2, -1);
			seg.modify (1, 1, n * 2, line[i].y2, -1, 1); seg.modify (1, 1, n * 2, line[i].y1, -1, 2);
		}
	}
	for (int i = 1; i <= n; i ++ ) deg[i] -- ;
	// for (int i = 1; i <= n; i++) write(deg[i], " \n"[i == n]);
	ll he = 0;
	// for (int i = 1; i <= n; i ++ ) he += deg[i];
	// he *= (n - 2);
	// for (int i = 1; i <= n; i ++ ) he -= 2 * C (deg[i], 2);
	for (int i = 1; i <= n; i++) he += deg[i] * (n - 1 - deg[i]);
	he /= 2;
	write(C(n, 3) - he - sum);
	flush();
	return 0;
}
/*
6
2 12 11 12
10 11 1 7
4 5 5 8
6 13 3 15
1 3 9 10
9 15 6 13
*/

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 40692kb

input:

5
1 5 1 5
4 8 2 6
3 7 3 7
2 6 28 32
42 46 42 46

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 0ms
memory: 38596kb

input:

6
1 8 6 10
2 5 3 12
3 4 15 20
0 9 2 22
-5 22 -2 23
-7 11 -1 17

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 0ms
memory: 38660kb

input:

10
-114 -46 148 199
-27 187 -26 190
-64 -16 151 228
-162 -44 -107 -96
45 185 -197 -128
100 180 -23 222
-152 138 52 181
141 193 -109 87
-87 175 -35 123
-110 227 -73 -44

output:

41

result:

ok 1 number(s): "41"

Test #4:

score: 0
Accepted
time: 0ms
memory: 38552kb

input:

10
-41 251 194 288
-194 69 -194 130
-17 23 -74 -60
-321 -236 89 298
-55 233 53 137
-32 114 -46 -24
-183 312 -286 322
-205 5 -222 67
14 119 -126 15
-76 57 -122 27

output:

20

result:

ok 1 number(s): "20"

Test #5:

score: 0
Accepted
time: 0ms
memory: 36548kb

input:

10
-68 10 22 87
30 89 -97 82
-52 25 -22 76
-20 95 21 25
-3 2 -7 45
-98 -56 -15 16
-79 -11 -73 -29
-71 59 -67 -40
-78 -46 -81 85
-62 -23 -90 -59

output:

24

result:

ok 1 number(s): "24"

Test #6:

score: 0
Accepted
time: 0ms
memory: 36484kb

input:

5
5 10 -15 -5
-11 6 2 13
7 8 -9 -2
-2 0 -3 10
-13 3 0 8

output:

0

result:

ok 1 number(s): "0"

Test #7:

score: 0
Accepted
time: 2ms
memory: 40684kb

input:

20
-12 9 10 21
-14 15 4 20
-3 22 12 29
-15 -13 -10 2
-5 14 -25 23
-6 28 -16 18
-7 24 -28 -21
25 26 -20 -2
-26 -11 -30 28
18 30 -27 -12
7 12 -17 -3
-23 -18 -9 -5
-22 8 9 25
-10 27 -24 -4
-4 10 17 24
2 23 -29 6
-24 19 26 27
-2 17 1 8
-8 16 -23 15
-19 -1 3 16

output:

300

result:

ok 1 number(s): "300"

Test #8:

score: 0
Accepted
time: 0ms
memory: 38636kb

input:

100
119 194 50 138
-42 74 -161 189
172 179 -127 35
-80 -74 -28 -8
-158 -88 42 155
7 182 41 123
-48 61 -100 -39
56 171 -154 -104
63 109 -27 5
96 107 -199 171
-110 98 142 159
-189 79 -62 97
148 159 -69 120
-11 155 -31 40
-1 1 -81 -48
125 130 74 179
-144 140 -70 154
-123 -19 -45 -37
-69 50 -121 -64
-18...

output:

30008

result:

ok 1 number(s): "30008"

Test #9:

score: 0
Accepted
time: 0ms
memory: 38732kb

input:

100
-127 147 -71 149
-76 75 -135 34
32 137 -154 -37
-102 67 28 125
-3 142 -102 -81
92 112 13 58
-22 118 -143 106
-1 146 19 156
23 93 -90 -43
84 132 40 119
-65 29 -74 26
79 88 121 148
-158 -12 -107 -51
-32 115 -96 -87
-153 -104 -9 68
-130 -129 -156 159
-123 156 -69 -2
-134 -83 -138 76
152 153 -27 117...

output:

36432

result:

ok 1 number(s): "36432"

Test #10:

score: 0
Accepted
time: 0ms
memory: 38628kb

input:

50
2 55 -27 -12
-22 92 -11 43
-7 15 3 98
-57 -10 -89 95
-13 -1 -45 6
-93 31 35 61
5 87 -70 -62
-95 19 -38 63
-75 100 -16 -5
-85 23 19 30
-28 96 -57 16
-63 47 -74 74
-20 65 -13 53
-17 67 -33 99
-87 60 -83 -26
-16 30 -64 92
-6 83 -56 64
-89 81 -81 -67
-25 88 -28 73
42 73 -7 22
-82 -72 -60 41
-49 9 36 ...

output:

3163

result:

ok 1 number(s): "3163"

Test #11:

score: 0
Accepted
time: 0ms
memory: 38588kb

input:

80
-49 -30 -69 41
-18 18 -19 109
-105 5 43 55
-23 53 26 65
-51 -46 -43 70
-33 55 -30 118
26 77 -97 -81
-69 108 -102 22
-100 84 -46 -37
45 102 -8 116
-11 19 27 117
-85 115 1 21
-53 -37 -39 -6
12 46 -51 105
2 112 -74 111
49 73 -95 97
-91 -34 -54 99
-103 -17 -62 60
-120 34 107 112
-65 91 37 54
0 29 -11...

output:

18042

result:

ok 1 number(s): "18042"

Test #12:

score: 0
Accepted
time: 0ms
memory: 38640kb

input:

100
-841118249 54124743 -626326499 268957660
-67982407 863071822 -701390018 -698615688
-442643513 576076137 -764229963 551005051
431006196 814541207 -59789787 297920747
-43726137 776889568 123191521 355546306
449575877 539401232 -547154377 156487400
-242017904 -56664269 71627074 636983445
-533630763...

output:

33574

result:

ok 1 number(s): "33574"

Test #13:

score: 0
Accepted
time: 2ms
memory: 38712kb

input:

200
-159856875 589617180 -91740528 827012068
-3244468 100974204 -204897309 624235032
740363419 811458184 -770093768 -459183292
-748577744 537657877 -919036011 26850784
-674800746 -335189105 -487556614 623807767
-759398571 -749755285 -236633574 905693829
-112618074 250091661 520796982 549786377
-6798...

output:

247012

result:

ok 1 number(s): "247012"

Test #14:

score: 0
Accepted
time: 0ms
memory: 38672kb

input:

300
-911895578 -569581980 147878148 795131888
-661123414 -528441116 242053045 343472902
-76629649 803750439 773718158 980952637
260774546 366805612 -674049855 -181475940
-626652074 -421458352 -803337455 840191725
-244053740 184891420 -345099744 -169202563
-610128030 -226308036 -999353606 -735065818
...

output:

1004267

result:

ok 1 number(s): "1004267"

Test #15:

score: 0
Accepted
time: 0ms
memory: 38716kb

input:

400
-830909902 861153449 -941780998 682464119
-220613384 281811674 -140128942 596875820
-960867515 -893622718 -236470184 975088832
-569688535 278858509 108993388 443221717
-918115043 -168115959 -891546816 880881705
-870818590 261647805 109139390 141318241
-96908206 -8404805 -791583380 -285895911
-97...

output:

2460666

result:

ok 1 number(s): "2460666"

Test #16:

score: 0
Accepted
time: 0ms
memory: 38680kb

input:

500
-298045711 417051395 -782949912 -678693884
-480285944 -450842739 -817278222 -611664178
-725485468 289384214 431167941 996431266
296942472 545694821 529862288 892036630
-966488219 380193728 -623285356 322011072
-937683357 -464585685 208749252 563378525
32491625 836408211 753208585 826252259
-9271...

output:

5193294

result:

ok 1 number(s): "5193294"

Test #17:

score: 0
Accepted
time: 0ms
memory: 38884kb

input:

600
203069778 837722424 -543331236 -415606770
-386104799 757616438 -358261261 800539792
-733193213 -527608855 -603691664 425304136
-338921825 20059141 -324920128 616502859
-962983894 390446329 -583704357 -355023895
-431981811 479704306 -982382342 571147558
-561868565 -81198337 -797621509 -722887724
...

output:

7677331

result:

ok 1 number(s): "7677331"

Test #18:

score: 0
Accepted
time: 0ms
memory: 38780kb

input:

700
-254001632 25368060 -303712559 -152519656
-616334153 -56358682 433198742 956414891
-497811166 117340991 124473038 629209786
38143104 724584029 -79933972 703143429
745553138 938756017 -899485198 -138639937
-524128202 -221247560 9913878 586701067
48201493 282944451 -810084792 -53484308
202718665 6...

output:

12296144

result:

ok 1 number(s): "12296144"

Test #19:

score: 0
Accepted
time: 4ms
memory: 39204kb

input:

2000
-580297120 549197350 -598869041 879583075
-954556446 -62577411 -803731747 335487679
-689376577 785481974 16605213 888665084
-320257042 329495972 491782245 670597773
347303891 363810780 -440727101 99207071
354771150 530453687 -499509583 407580550
-363375564 650395473 -31669850 374805738
-9452822...

output:

313938221

result:

ok 1 number(s): "313938221"

Test #20:

score: 0
Accepted
time: 12ms
memory: 40732kb

input:

5000
-591270635 510694320 83206315 186982934
-697045084 -198641774 -375097474 752780107
-702494041 -200162855 -980400671 -923640406
-418088873 614160702 -623846134 -30029692
-272220084 518501838 -655904295 910767648
132927998 169713224 -675737799 -241853350
-538544803 -21550989 -714286937 -378442715...

output:

4558798032

result:

ok 1 number(s): "4558798032"

Test #21:

score: 0
Accepted
time: 28ms
memory: 46220kb

input:

10000
-201957185 118307450 -266375727 745966927
-736796598 75870065 471448807 594899198
-723586512 655989486 -73931815 245738688
-984988678 906250107 -589969172 517901031
-799809845 759583842 -220308400 398919680
-488446145 777931876 -676675087 -646648304
-876126176 -209651494 97786386 417944889
-36...

output:

36473099188

result:

ok 1 number(s): "36473099188"

Test #22:

score: 0
Accepted
time: 479ms
memory: 96720kb

input:

100000
226564148 486750691 -450254989 466727591
-502609877 -3752654 -440437681 500722941
-983190884 202308173 -544037788 -57081694
70916258 294751219 -290590129 873004953
723830371 964799716 -177364196 91139653
534342079 544990348 -632680846 666392090
-906658216 -423388042 -210927029 816790191
-8911...

output:

37183181239478

result:

ok 1 number(s): "37183181239478"

Test #23:

score: 0
Accepted
time: 1100ms
memory: 156380kb

input:

200000
367031365 380518706 -590955530 -145803774
30572786 915595795 -492108235 -76144590
-206184243 482187782 166234680 411061068
-160448386 93871862 -690036834 -413709526
-928088982 -582615677 -200003644 653596324
-391991446 -148169696 58890373 876425548
-657005544 13191918 -518772663 979443176
739...

output:

297858270782347

result:

ok 1 number(s): "297858270782347"

Test #24:

score: 0
Accepted
time: 1061ms
memory: 158028kb

input:

200000
-225636631 970953278 -551217116 569289094
-386591114 874277277 227774719 368531094
414874571 744129011 167365910 489367267
-101394885 252157771 -935558478 -921784933
-332996759 193645059 450365810 615535977
534268382 839442266 -651344308 973612355
-812834130 -463779096 -908813542 988376312
-8...

output:

300088515091234

result:

ok 1 number(s): "300088515091234"

Test #25:

score: 0
Accepted
time: 1073ms
memory: 156324kb

input:

200000
-760211388 42056124 187370466 662010342
-950028200 909542645 -810431015 -267421984
-256202835 671322162 -356383109 -101939354
260772572 708149873 -130443586 834223039
-471047217 750658799 -707049350 -400288110
-669122331 574041864 -200846059 112227901
-421966055 349825346 2584613 803301379
-7...

output:

299317567765471

result:

ok 1 number(s): "299317567765471"

Test #26:

score: 0
Accepted
time: 1061ms
memory: 156348kb

input:

200000
-607025449 422340287 208590202 787872296
-560243992 795908494 171563580 561131367
-21277979 499711837 -990850781 315353074
-932236149 893694354 -676563240 -294476635
-568879047 -189586820 -422384620 899084426
-131595505 988329603 -280713171 612591604
-487739224 -162196229 -416733396 581458227...

output:

299452022544391

result:

ok 1 number(s): "299452022544391"

Test #27:

score: 0
Accepted
time: 1075ms
memory: 156140kb

input:

200000
-353795267 -72450692 -668444954 833598622
143622250 863303762 -643752691 755639156
-499956318 -277725570 -813946559 -798373012
84149596 816059259 -790850687 -741312049
-147276564 969847415 -85091488 735030540
-571153407 948556121 337581491 457060648
-581429766 675144296 569058303 574376014
23...

output:

299139726450686

result:

ok 1 number(s): "299139726450686"

Test #28:

score: 0
Accepted
time: 1027ms
memory: 158200kb

input:

200000
-617996869 279869790 355290630 842758249
411598902 577463371 -805271492 561017689
768119544 849969331 -835412646 801721101
612385160 985328506 314735514 411888407
275797722 666732704 -229323442 482005409
-461351447 -91443934 -466036854 984932471
28297600 884470395 -393202949 1928682
-26489602...

output:

300307736868420

result:

ok 1 number(s): "300307736868420"

Test #29:

score: 0
Accepted
time: 1078ms
memory: 158708kb

input:

200000
-219806 87059 -331800 15467
-398900 -156419 -191467 -31392
-180415 190637 -56257 369691
-251590 -239726 -145539 311463
-383962 -337339 125245 270519
-397922 -120176 -191769 376026
-36330 275900 -291524 27697
339087 388026 -255842 -177030
-37402 47488 -258929 255008
-323046 -89972 -386706 1531...

output:

297006755898278

result:

ok 1 number(s): "297006755898278"

Test #30:

score: 0
Accepted
time: 1058ms
memory: 158944kb

input:

200000
-64205 415759 18371 176549
-356219 455332 182159 380632
-148533 -6548 -307252 466748
-433538 -197819 12331 217327
-366031 271135 -442357 -139359
29091 499051 -160979 448862
-3397 341051 -327855 461482
-435024 9154 104065 158233
102967 476382 -121788 322416
9360 475240 9803 284989
-175083 2965...

output:

296698907698133

result:

ok 1 number(s): "296698907698133"

Test #31:

score: 0
Accepted
time: 994ms
memory: 158136kb

input:

200000
-1087845 4754710 2899905 3507907
92042 719716 212637 1684307
-1807754 2196421 -4233981 -669938
-2872558 -407329 -3859314 -392538
-1981106 606603 -1402557 -767511
4567096 4785610 -135473 1068806
-2692479 -1839766 -2427870 928598
-3873136 4633760 -497884 2551791
-4980919 4103129 -3984158 202326...

output:

297707734978257

result:

ok 1 number(s): "297707734978257"

Test #32:

score: 0
Accepted
time: 1043ms
memory: 158456kb

input:

200000
-161706 123833 -337725 79849
-167211 -32288 -332709 -46049
-179529 -39672 -88309 204596
242670 265751 34087 140544
-104435 168695 -66676 203705
-304326 208485 83541 215514
-314871 287643 -151603 117949
-308301 133510 -147734 43907
-297458 87087 -148393 259194
-51666 244952 -327479 16194
-8009...

output:

298463780366978

result:

ok 1 number(s): "298463780366978"

Test #33:

score: 0
Accepted
time: 314ms
memory: 145760kb

input:

200000
1 200002 1 200002
2 200003 2 200003
3 200004 3 200004
4 200005 4 200005
5 200006 5 200006
6 200007 6 200007
7 200008 7 200008
8 200009 8 200009
9 200010 9 200010
10 200011 10 200011
11 200012 11 200012
12 200013 12 200013
13 200014 13 200014
14 200015 14 200015
15 200016 15 200016
16 200017 1...

output:

0

result:

ok 1 number(s): "0"

Test #34:

score: 0
Accepted
time: 329ms
memory: 138928kb

input:

199999
1 200001 1 200001
2 200002 2 200002
3 200003 3 200003
4 200004 4 200004
5 200005 5 200005
6 200006 6 200006
7 200007 7 200007
8 200008 8 200008
9 200009 9 200009
10 200010 10 200010
11 200011 11 200011
12 200012 12 200012
13 200013 13 200013
14 200014 14 200014
15 200015 15 200015
16 200016 1...

output:

0

result:

ok 1 number(s): "0"