QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#521597#8920. Восстание газонокосилокMilkcat100 ✓22ms16780kbC++141.1kb2024-08-16 12:56:012024-08-16 12:56:01

Judging History

This is the latest submission verdict.

  • [2024-08-16 12:56:01]
  • Judged
  • Verdict: 100
  • Time: 22ms
  • Memory: 16780kb
  • [2024-08-16 12:56:01]
  • Submitted

answer

#include <bits/stdc++.h>
#define REP(i, l, r) for (int i = (l); i <= (r); ++ i)
#define DEP(i, r, l) for (int i = (r); i >= (l); -- i)
#define fi first
#define se second
#define pb emplace_back
#define mems(x, v) memset((x), (v), sizeof(x))
using namespace std;
namespace Milkcat {
	typedef long long LL;
	typedef pair<LL, LL> pii;
	const int N = 1e6 + 5;
	LL n, rs, a[N], p[N], d[N], pr[N], sf[N];
	int main() {
		cin >> n;
		REP(i, 1, n) cin >> a[i] >> p[i] >> d[i];
		pr[0] = sf[n + 1] = 0, rs = 1e18;
		REP(i, 1, n) {
			pr[i] = pr[i - 1] + (d[i] < 0);
			if (i > 1 && a[i] - a[i - 1] > p[i - 1]) pr[i] = 1e18;
		}
		DEP(i, n, 1) {
			sf[i] = sf[i + 1] + (d[i] > 0);
			if (i < n && a[i + 1] - a[i] > p[i + 1]) sf[i] = 1e18;
		}
		REP(i, 1, n + 1)
			if (p[i - 1] + p[i] >= a[i] - a[i - 1]) rs = min(rs, pr[i - 1] + sf[i]);
		cout << (rs > 1e9 ? -1 : rs) << '\n';
		return 0;
	}
}
int main() {
//	freopen("a.in", "r", stdin);
//	freopen("a.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int T = 1;
	while (T --) Milkcat::main();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 23
Accepted

Test #1:

score: 23
Accepted
time: 1ms
memory: 11848kb

input:

10
0 9 1
1 6 1
2 4 1
3 2 1
4 3 1
5 4 -1
7 4 1
8 7 -1
9 4 1
10 7 1

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 23
Accepted
time: 1ms
memory: 11764kb

input:

10
0 3 1
1 5 -1
11 5 1
16 3 -1
22 8 -1
23 4 1
28 4 1
34 3 1
39 7 1
40 5 -1

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

score: 23
Accepted
time: 0ms
memory: 11832kb

input:

10
0 12 -1
1 2 1
14 18 -1
19 18 1
31 9 1
33 4 1
34 18 1
36 15 -1
46 15 -1
63 6 1

output:

-1

result:

ok 1 number(s): "-1"

Test #4:

score: 23
Accepted
time: 1ms
memory: 11780kb

input:

10
0 630608459 -1
99534806 668585190 -1
109086445 929464356 1
217136748 478194593 1
352297971 197486632 -1
365911158 539729730 1
461993653 781006864 -1
488768249 875897690 1
506991884 971941607 1
513148437 562630670 -1

output:

4

result:

ok 1 number(s): "4"

Test #5:

score: 23
Accepted
time: 1ms
memory: 11728kb

input:

6
0 9 1
1 7 1
3 7 1
4 3 -1
6 1 -1
7 7 -1

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 23
Accepted
time: 1ms
memory: 11772kb

input:

10
0 9 1
9 11 1
20 3 -1
23 1 1
24 18 1
42 6 -1
53 5 1
70 17 -1
76 6 -1
100 24 1

output:

4

result:

ok 1 number(s): "4"

Test #7:

score: 23
Accepted
time: 1ms
memory: 11848kb

input:

10
0 3 -1
2 4 -1
13 7 -1
21 9 -1
24 3 -1
27 4 1
33 6 -1
58 26 -1
68 11 -1
100 32 1

output:

4

result:

ok 1 number(s): "4"

Test #8:

score: 23
Accepted
time: 1ms
memory: 11860kb

input:

10
0 14620135 1
14619649 67492279 -1
82111877 92368562 1
174479944 44651960 1
219131755 66340745 1
305947635 20475928 1
484391538 178444404 1
496149253 11757753 -1
630583086 134434525 1
1000000000 369417252 -1

output:

4

result:

ok 1 number(s): "4"

Test #9:

score: 23
Accepted
time: 1ms
memory: 11876kb

input:

10
0 11151 -1
11151 1830 -1
12981 1225 -1
22537 8331 -1
32662 10125 -1
39510 6848 -1
62604 23094 1
68558 5954 1
82045 13487 1
123456 41410 -1

output:

-1

result:

ok 1 number(s): "-1"

Test #10:

score: 23
Accepted
time: 1ms
memory: 11860kb

input:

10
0 89628821 1
89628750 39194053 1
128823848 110237151 1
239060899 122905660 1
361966024 72284352 -1
434249475 22842655 -1
579153572 122062369 1
621403934 42251228 1
680140325 58737342 -1
1000000000 319859750 1

output:

-1

result:

ok 1 number(s): "-1"

Test #11:

score: 23
Accepted
time: 1ms
memory: 11732kb

input:

10
0 1 1
1 1 1
2 1 1
3 1 1
4 1 1
5 1 -1
6 1 1
7 1 -1
8 1 1
9 1 -1

output:

2

result:

ok 1 number(s): "2"

Subtask #2:

score: 16
Accepted

Test #12:

score: 16
Accepted
time: 1ms
memory: 11780kb

input:

10
0 2 1
6 5 1
30 6 1
43 8 1
48 3 1
50 9 1
60 10 1
72 7 1
77 8 1
80 7 1

output:

-1

result:

ok 1 number(s): "-1"

Test #13:

score: 16
Accepted
time: 1ms
memory: 11784kb

input:

100
0 9706359 1
4010340 5139532 1
9155946 4085372 1
10589722 5738127 1
23419068 2070230 1
27738854 6288025 1
33937892 2918930 1
34311768 4657439 1
40823439 5939122 1
45032364 6110475 1
46403154 1003945 1
59136098 5006589 1
67216994 120288 1
71862076 4028359 1
76552553 4451765 1
82049610 9022832 1
82...

output:

-1

result:

ok 1 number(s): "-1"

Test #14:

score: 16
Accepted
time: 3ms
memory: 13912kb

input:

10000
0 76431 1
100748 63751 1
420013 89748 1
562526 29316 1
836219 61301 1
897326 11302 1
1017865 36657 1
1046067 48760 1
1168440 95263 1
1330591 38297 1
1351586 50213 1
1576552 57883 1
1670802 64290 1
1750320 94404 1
1868468 7077 1
1880574 15664 1
1904278 74259 1
1924402 84461 1
1947449 31237 1
19...

output:

-1

result:

ok 1 number(s): "-1"

Test #15:

score: 16
Accepted
time: 14ms
memory: 14620kb

input:

100000
0 277 1
405 2794 1
502 1908 1
1648 3819 1
1663 4398 1
3354 8921 1
4701 6214 1
5011 3363 1
5377 9189 1
8672 2125 1
10120 8281 1
10465 4668 1
11216 2049 1
11639 3884 1
12923 7714 1
13635 6203 1
14271 2997 1
14603 4363 1
14780 1734 1
15423 6515 1
16631 3447 1
19170 2303 1
19822 8363 1
19858 4828...

output:

-1

result:

ok 1 number(s): "-1"

Test #16:

score: 16
Accepted
time: 13ms
memory: 16780kb

input:

100000
0 11 1
11 7 1
18 17 1
35 18 1
53 2 1
55 4 1
59 15 1
74 3 1
77 2 1
79 17 1
96 4 1
100 8 1
108 16 1
124 3 1
127 33 1
160 2 1
162 1 1
163 2 1
165 10 1
175 9 1
184 10 1
194 8 1
202 7 1
209 6 1
215 6 1
221 16 1
237 8 1
245 1 1
246 10 1
256 14 1
270 2 1
272 5 1
277 18 1
295 10 1
305 12 1
317 1 1
31...

output:

13280

result:

ok 1 number(s): "13280"

Test #17:

score: 16
Accepted
time: 16ms
memory: 14668kb

input:

100000
0 11315 1
11143 9723 1
20710 21305 1
41885 2794 1
43739 14923 1
57896 8739 1
66585 10844 1
76528 5892 1
81444 2450 1
83310 10048 1
92933 16884 1
109743 7692 1
116494 9714 1
125967 2330 1
127951 26149 1
153811 3366 1
157009 2512 1
158935 1906 1
159945 10708 1
169924 31940 1
201534 32069 1
2335...

output:

92375

result:

ok 1 number(s): "92375"

Test #18:

score: 16
Accepted
time: 14ms
memory: 16504kb

input:

100000
0 6 1
6 4 1
10 4 1
14 5 1
19 11 1
30 1 1
31 5 1
36 11 1
47 15 1
62 11 1
73 16 1
89 17 1
106 4 1
110 6 1
116 2 1
118 8 1
126 6 1
132 19 1
151 12 1
163 6 1
169 9 1
178 8 1
186 5 1
191 4 1
195 14 1
209 14 1
223 46 1
269 13 1
282 5 1
287 14 1
301 15 1
316 10 1
326 6 1
332 13 1
345 30 1
375 9 1
38...

output:

-1

result:

ok 1 number(s): "-1"

Test #19:

score: 16
Accepted
time: 12ms
memory: 16296kb

input:

100000
0 1899 1
1395 7477 1
8667 26043 1
33931 13481 1
47321 3659 1
50108 641 1
50149 1702 1
51465 15589 1
66263 16523 1
81847 5703 1
87498 21106 1
108353 7372 1
115647 5059 1
120690 20525 1
141163 14055 1
154566 19377 1
173068 1717 1
174229 32275 1
206446 17734 1
223453 19194 1
242480 2286 1
244287...

output:

-1

result:

ok 1 number(s): "-1"

Subtask #3:

score: 17
Accepted

Dependency #1:

100%
Accepted

Test #20:

score: 17
Accepted
time: 0ms
memory: 11792kb

input:

1000
0 551525 -1
342965 314510 -1
881133 954277 -1
948047 920531 1
1076015 141846 1
1257798 477540 1
1264130 742614 1
1442897 581444 1
1470658 687724 1
1601603 730583 1
1844560 526462 1
1948263 155113 -1
2022891 241304 1
2084831 192423 1
2143483 984812 -1
2236413 987683 -1
2306502 710989 -1
2316006 ...

output:

-1

result:

ok 1 number(s): "-1"

Test #21:

score: 17
Accepted
time: 0ms
memory: 11792kb

input:

1000
0 45162413 1
342401 46695466 1
548981 19989399 -1
925520 26865055 1
1172037 93802153 -1
1964568 92106914 1
1993378 81287679 -1
2226931 63863042 -1
2239482 39689275 1
2602069 14180433 -1
3885734 15947778 1
4522849 26517095 -1
4614325 22392700 1
5279282 24414687 -1
5293844 42291416 1
5500802 4563...

output:

-1

result:

ok 1 number(s): "-1"

Test #22:

score: 17
Accepted
time: 1ms
memory: 11884kb

input:

1000
0 396952019 1
155603 571886325 1
516329 218089554 1
1794531 484487361 1
2156521 117197825 1
2305058 588616756 1
2817167 84205197 -1
3456345 628750664 -1
4059916 420899034 -1
4282685 493025898 -1
5947807 779951487 -1
6390081 86541049 -1
8064274 442664261 1
8154025 537189836 1
8680373 390719403 1...

output:

483

result:

ok 1 number(s): "483"

Test #23:

score: 17
Accepted
time: 1ms
memory: 11788kb

input:

1000
0 376 1
376 268 1
644 798 -1
1442 1873 -1
3315 1419 1
4734 1232 1
5966 579 -1
6545 441 1
6986 354 -1
7340 264 -1
7604 3495 -1
11099 416 1
11515 637 -1
12152 3436 1
15588 357 1
15945 1138 1
17083 4341 1
21424 451 -1
21875 301 -1
22176 131 1
22307 735 1
23042 205 -1
23247 228 -1
23475 169 1
23644...

output:

494

result:

ok 1 number(s): "494"

Test #24:

score: 17
Accepted
time: 1ms
memory: 11912kb

input:

1000
0 1650990 -1
1650191 555386 -1
2205511 272659 1
2478020 1070275 1
3547928 197201 1
3744164 712552 -1
4455962 332055 1
4787067 639518 -1
5426364 1870761 -1
7296935 1686895 1
8982907 629075 1
9611733 985386 1
10596951 1222015 -1
11818103 958691 1
12776710 2108167 1
14884351 2002400 -1
16886333 14...

output:

505

result:

ok 1 number(s): "505"

Test #25:

score: 17
Accepted
time: 1ms
memory: 11880kb

input:

1000
0 1090 -1
1090 309 -1
1399 599 1
1998 401 1
2399 1270 1
3669 774 1
4443 555 1
4998 357 -1
5355 3 1
5358 3109 1
8467 105 1
8572 231 -1
8803 56 1
8859 2296 -1
11155 1724 -1
12879 705 -1
13584 195 -1
13779 442 1
14221 2528 -1
16749 329 -1
17078 67 1
17145 1637 -1
18782 774 1
19556 215 -1
19771 122...

output:

-1

result:

ok 1 number(s): "-1"

Test #26:

score: 17
Accepted
time: 1ms
memory: 11932kb

input:

1000
0 364111 -1
363551 835990 -1
1198698 449599 -1
1648186 2362786 -1
4010048 676796 1
4686168 223715 -1
4911041 3516023 -1
8426164 842730 -1
9268708 1719438 1
10987815 2328475 -1
13315429 2207825 -1
15522504 2685802 1
18207862 74151 -1
18281158 88215 -1
18368700 1994193 -1
20361902 600523 1
209621...

output:

-1

result:

ok 1 number(s): "-1"

Test #27:

score: 17
Accepted
time: 1ms
memory: 11860kb

input:

1000
0 1 -1
1 1 -1
2 1 -1
3 1 -1
4 1 -1
5 1 -1
6 1 -1
7 1 -1
8 1 -1
9 1 -1
10 1 -1
11 1 -1
12 1 -1
13 1 -1
14 1 -1
15 1 -1
16 1 -1
17 1 -1
18 1 -1
19 1 -1
20 1 -1
21 1 -1
22 1 -1
23 1 -1
24 1 -1
25 1 -1
26 1 -1
27 1 -1
28 1 -1
29 1 -1
30 1 -1
31 1 -1
32 1 -1
33 1 -1
34 1 -1
35 1 -1
36 1 -1
37 1 -1
3...

output:

6

result:

ok 1 number(s): "6"

Test #28:

score: 17
Accepted
time: 1ms
memory: 11880kb

input:

1000
0 1 1
1 1 1
2 1 1
3 1 1
4 1 1
5 1 1
6 1 1
7 1 1
8 1 1
9 1 1
10 1 1
11 1 1
12 1 1
13 1 1
14 1 1
15 1 1
16 1 1
17 1 1
18 1 1
19 1 1
20 1 1
21 1 1
22 1 1
23 1 1
24 1 1
25 1 1
26 1 1
27 1 1
28 1 1
29 1 1
30 1 1
31 1 1
32 1 1
33 1 1
34 1 1
35 1 1
36 1 1
37 1 1
38 1 1
39 1 1
40 1 1
41 1 1
42 1 1
43 1...

output:

4

result:

ok 1 number(s): "4"

Test #29:

score: 17
Accepted
time: 0ms
memory: 11736kb

input:

1000
0 1 1
1 1 1
2 1 1
3 1 1
4 1 1
5 1 1
6 1 1
7 1 1
8 1 1
9 1 1
10 1 1
11 1 1
12 1 1
13 1 1
14 1 1
15 1 1
16 1 1
17 1 1
18 1 1
19 1 1
20 1 1
21 1 1
22 1 1
23 1 1
24 1 1
25 1 1
26 1 1
27 1 1
28 1 1
29 1 1
30 1 1
31 1 1
32 1 1
33 1 1
34 1 1
35 1 1
36 1 1
37 1 1
38 1 1
39 1 1
40 1 1
41 1 1
42 1 1
43 1...

output:

6

result:

ok 1 number(s): "6"

Test #30:

score: 17
Accepted
time: 0ms
memory: 11876kb

input:

1000
0 1 -1
1 1 -1
2 1 -1
3 1 -1
4 1 -1
5 1 -1
6 1 -1
7 1 -1
8 1 -1
9 1 -1
10 1 -1
11 1 -1
12 1 -1
13 1 -1
14 1 -1
15 1 -1
16 1 -1
17 1 -1
18 1 -1
19 1 -1
20 1 -1
21 1 -1
22 1 -1
23 1 -1
24 1 -1
25 1 -1
26 1 -1
27 1 -1
28 1 -1
29 1 -1
30 1 -1
31 1 -1
32 1 -1
33 1 -1
34 1 -1
35 1 -1
36 1 -1
37 1 -1
3...

output:

47

result:

ok 1 number(s): "47"

Test #31:

score: 17
Accepted
time: 0ms
memory: 11880kb

input:

1000
0 1 1
1 1 1
2 1 1
3 1 1
4 1 1
5 1 1
6 1 1
7 1 1
8 1 1
9 1 1
10 1 1
11 1 1
12 1 1
13 1 1
14 1 1
15 1 1
16 1 1
17 1 1
18 1 1
19 1 1
20 1 -1
21 1 1
22 1 1
23 1 1
24 1 1
25 1 1
26 1 1
27 1 1
28 1 1
29 1 1
30 1 1
31 1 1
32 1 1
33 1 1
34 1 1
35 1 1
36 1 1
37 1 -1
38 1 1
39 1 1
40 1 1
41 1 1
42 1 1
43...

output:

37

result:

ok 1 number(s): "37"

Test #32:

score: 17
Accepted
time: 0ms
memory: 11856kb

input:

1000
0 1 1
1 1 1
2 1 1
3 1 1
4 1 1
5 1 1
6 1 1
7 1 1
8 1 1
9 1 1
10 1 1
11 1 1
12 1 1
13 1 1
14 1 1
15 1 1
16 1 1
17 1 1
18 1 1
19 1 1
20 1 1
21 1 1
22 1 1
23 1 1
24 1 1
25 1 1
26 1 1
27 1 1
28 1 1
29 1 1
30 1 1
31 1 1
32 1 1
33 1 1
34 1 1
35 1 -1
36 1 1
37 1 1
38 1 1
39 1 1
40 1 1
41 1 1
42 1 1
43 ...

output:

50

result:

ok 1 number(s): "50"

Subtask #4:

score: 13
Accepted

Test #33:

score: 13
Accepted
time: 1ms
memory: 11800kb

input:

1000
0 1 1
1 1 1
2 1 1
3 1 1
4 1 1
5 1 1
6 1 1
7 1 1
8 1 1
9 1 1
10 1 1
11 1 -1
12 1 1
13 1 1
14 1 1
15 1 1
16 1 -1
17 1 -1
18 1 -1
19 1 1
20 1 1
21 1 1
22 1 1
23 1 -1
24 1 1
25 1 -1
26 1 -1
27 1 1
28 1 -1
29 1 1
30 1 1
31 1 -1
32 1 1
33 1 -1
34 1 -1
35 1 1
36 1 1
37 1 1
38 1 -1
39 1 -1
40 1 -1
41 1...

output:

460

result:

ok 1 number(s): "460"

Test #34:

score: 13
Accepted
time: 13ms
memory: 16664kb

input:

100000
0 1 -1
1 1 1
2 1 1
3 1 1
4 1 -1
5 1 1
6 1 -1
7 1 -1
8 1 1
9 1 1
10 1 -1
11 1 1
12 1 -1
13 1 1
14 1 1
15 1 1
16 1 -1
17 1 1
18 1 -1
19 1 -1
20 1 1
21 1 1
22 1 1
23 1 1
24 1 -1
25 1 -1
26 1 1
27 1 -1
28 1 1
29 1 1
30 1 1
31 1 1
32 1 1
33 1 -1
34 1 1
35 1 -1
36 1 -1
37 1 -1
38 1 -1
39 1 -1
40 1 ...

output:

49840

result:

ok 1 number(s): "49840"

Test #35:

score: 13
Accepted
time: 12ms
memory: 15952kb

input:

100000
0 1 -1
1 1 -1
2 1 -1
3 1 -1
4 1 -1
5 1 -1
6 1 -1
7 1 -1
8 1 -1
9 1 -1
10 1 -1
11 1 -1
12 1 -1
13 1 -1
14 1 -1
15 1 -1
16 1 -1
17 1 -1
18 1 -1
19 1 -1
20 1 -1
21 1 -1
22 1 -1
23 1 -1
24 1 -1
25 1 -1
26 1 -1
27 1 -1
28 1 -1
29 1 -1
30 1 -1
31 1 -1
32 1 -1
33 1 -1
34 1 -1
35 1 -1
36 1 -1
37 1 -1...

output:

504

result:

ok 1 number(s): "504"

Test #36:

score: 13
Accepted
time: 7ms
memory: 16068kb

input:

100000
0 1 1
1 1 1
2 1 1
3 1 1
4 1 1
5 1 1
6 1 1
7 1 1
8 1 1
9 1 1
10 1 1
11 1 1
12 1 1
13 1 1
14 1 1
15 1 1
16 1 1
17 1 1
18 1 1
19 1 1
20 1 1
21 1 1
22 1 1
23 1 1
24 1 1
25 1 1
26 1 1
27 1 1
28 1 1
29 1 1
30 1 1
31 1 1
32 1 1
33 1 1
34 1 1
35 1 1
36 1 1
37 1 1
38 1 1
39 1 1
40 1 1
41 1 1
42 1 1
43...

output:

491

result:

ok 1 number(s): "491"

Test #37:

score: 13
Accepted
time: 8ms
memory: 16104kb

input:

100000
0 1 1
1 1 1
2 1 1
3 1 1
4 1 1
5 1 1
6 1 1
7 1 1
8 1 1
9 1 1
10 1 1
11 1 1
12 1 1
13 1 1
14 1 1
15 1 1
16 1 1
17 1 1
18 1 1
19 1 1
20 1 1
21 1 1
22 1 1
23 1 1
24 1 1
25 1 1
26 1 1
27 1 1
28 1 1
29 1 1
30 1 1
31 1 1
32 1 1
33 1 1
34 1 1
35 1 1
36 1 1
37 1 1
38 1 -1
39 1 -1
40 1 1
41 1 1
42 1 1
...

output:

522

result:

ok 1 number(s): "522"

Test #38:

score: 13
Accepted
time: 12ms
memory: 16296kb

input:

100000
0 1 -1
1 1 -1
2 1 -1
3 1 -1
4 1 -1
5 1 -1
6 1 -1
7 1 -1
8 1 -1
9 1 -1
10 1 -1
11 1 -1
12 1 -1
13 1 -1
14 1 -1
15 1 -1
16 1 -1
17 1 1
18 1 -1
19 1 -1
20 1 -1
21 1 -1
22 1 -1
23 1 -1
24 1 -1
25 1 -1
26 1 -1
27 1 -1
28 1 -1
29 1 -1
30 1 -1
31 1 1
32 1 -1
33 1 -1
34 1 -1
35 1 -1
36 1 -1
37 1 -1
3...

output:

4724

result:

ok 1 number(s): "4724"

Test #39:

score: 13
Accepted
time: 8ms
memory: 16768kb

input:

100000
0 1 1
1 1 1
2 1 1
3 1 1
4 1 1
5 1 1
6 1 1
7 1 1
8 1 1
9 1 1
10 1 1
11 1 1
12 1 1
13 1 1
14 1 1
15 1 1
16 1 1
17 1 1
18 1 1
19 1 1
20 1 1
21 1 -1
22 1 1
23 1 1
24 1 1
25 1 1
26 1 1
27 1 1
28 1 1
29 1 1
30 1 1
31 1 1
32 1 1
33 1 1
34 1 1
35 1 1
36 1 1
37 1 -1
38 1 1
39 1 1
40 1 1
41 1 1
42 1 1
...

output:

4731

result:

ok 1 number(s): "4731"

Test #40:

score: 13
Accepted
time: 12ms
memory: 14300kb

input:

100000
0 1 1
1 1 1
2 1 1
3 1 1
4 1 1
5 1 1
6 1 1
7 1 1
8 1 -1
9 1 1
10 1 1
11 1 1
12 1 1
13 1 1
14 1 1
15 1 1
16 1 -1
17 1 1
18 1 1
19 1 1
20 1 1
21 1 1
22 1 1
23 1 1
24 1 1
25 1 1
26 1 1
27 1 1
28 1 1
29 1 1
30 1 1
31 1 1
32 1 1
33 1 1
34 1 1
35 1 1
36 1 1
37 1 1
38 1 1
39 1 1
40 1 1
41 1 1
42 1 1
...

output:

4665

result:

ok 1 number(s): "4665"

Subtask #5:

score: 14
Accepted

Test #41:

score: 14
Accepted
time: 13ms
memory: 16668kb

input:

100000
0 1000000000 1
8647 1000000000 -1
17560 1000000000 -1
41175 1000000000 1
47287 1000000000 1
55634 1000000000 -1
60818 1000000000 1
67825 1000000000 1
69518 1000000000 1
71061 1000000000 1
84754 1000000000 -1
100792 1000000000 -1
118181 1000000000 -1
123883 1000000000 -1
125803 1000000000 -1
1...

output:

49751

result:

ok 1 number(s): "49751"

Test #42:

score: 14
Accepted
time: 11ms
memory: 16276kb

input:

100000
0 1000000000 -1
14302 1000000000 -1
16639 1000000000 -1
18100 1000000000 -1
19451 1000000000 -1
29667 1000000000 -1
39873 1000000000 -1
44265 1000000000 -1
52392 1000000000 -1
66052 1000000000 -1
95044 1000000000 -1
109076 1000000000 -1
109384 1000000000 -1
110812 1000000000 -1
111953 1000000...

output:

510

result:

ok 1 number(s): "510"

Test #43:

score: 14
Accepted
time: 14ms
memory: 16740kb

input:

100000
0 1000000000 1
4788 1000000000 1
4948 1000000000 1
5060 1000000000 1
10795 1000000000 1
51950 1000000000 1
107040 1000000000 1
111253 1000000000 1
123929 1000000000 1
126952 1000000000 1
131286 1000000000 1
132430 1000000000 1
138397 1000000000 1
141231 1000000000 1
148704 1000000000 1
148760...

output:

529

result:

ok 1 number(s): "529"

Test #44:

score: 14
Accepted
time: 18ms
memory: 16052kb

input:

100000
0 1000000000 1
3512 1000000000 1
5901 1000000000 1
6371 1000000000 1
30382 1000000000 1
51973 1000000000 1
55046 1000000000 1
58047 1000000000 1
66067 1000000000 1
68633 1000000000 1
70063 1000000000 1
77545 1000000000 1
82127 1000000000 1
90951 1000000000 1
111170 1000000000 1
116907 1000000...

output:

506

result:

ok 1 number(s): "506"

Test #45:

score: 14
Accepted
time: 14ms
memory: 16492kb

input:

100000
0 1000000000 -1
11129 1000000000 -1
29900 1000000000 -1
36114 1000000000 -1
60052 1000000000 -1
61322 1000000000 -1
71619 1000000000 -1
75924 1000000000 -1
80854 1000000000 -1
103774 1000000000 -1
108986 1000000000 -1
110839 1000000000 -1
119748 1000000000 -1
136500 1000000000 -1
137428 10000...

output:

4724

result:

ok 1 number(s): "4724"

Test #46:

score: 14
Accepted
time: 14ms
memory: 16724kb

input:

100000
0 1000000000 1
122 1000000000 1
5532 1000000000 1
9948 1000000000 1
27632 1000000000 1
45706 1000000000 1
61260 1000000000 1
65665 1000000000 1
73737 1000000000 1
78718 1000000000 1
95598 1000000000 1
96065 1000000000 1
104398 1000000000 1
106266 1000000000 1
111258 1000000000 1
113409 100000...

output:

4694

result:

ok 1 number(s): "4694"

Test #47:

score: 14
Accepted
time: 18ms
memory: 16224kb

input:

100000
0 1000000000 1
7153 1000000000 1
18441 1000000000 1
28530 1000000000 1
31433 1000000000 1
41694 1000000000 1
43034 1000000000 1
56709 1000000000 1
74141 1000000000 1
82138 1000000000 1
100344 1000000000 1
100384 1000000000 1
103516 1000000000 1
112507 1000000000 1
121663 1000000000 1
131749 1...

output:

4768

result:

ok 1 number(s): "4768"

Subtask #6:

score: 17
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #48:

score: 17
Accepted
time: 12ms
memory: 16672kb

input:

100000
0 4047 1
1380 401 1
1707 691 -1
2479 8092 -1
4993 4951 -1
11608 1258 -1
14820 6283 1
15052 9326 -1
18679 2818 1
22474 6318 1
22837 1574 1
26711 5603 -1
28086 6914 -1
44562 2188 1
52931 9239 1
53778 1179 -1
70972 3128 -1
72578 742 1
77286 2205 -1
81337 3175 -1
82469 7204 -1
87693 8621 -1
92771...

output:

-1

result:

ok 1 number(s): "-1"

Test #49:

score: 17
Accepted
time: 12ms
memory: 16664kb

input:

100000
0 49911 -1
12188 60156 1
23515 1333 1
25622 37915 1
32020 22223 -1
32108 74000 -1
33378 96908 -1
44374 29465 -1
50454 29861 1
76626 81515 -1
82443 6824 -1
86042 62925 1
110200 83286 -1
117977 25818 1
137202 59877 1
147110 20771 -1
148601 84542 -1
152203 68587 -1
152857 31296 -1
157236 61385 1...

output:

-1

result:

ok 1 number(s): "-1"

Test #50:

score: 17
Accepted
time: 16ms
memory: 14692kb

input:

100000
0 190385 1
1348 719522 -1
13061 517665 1
18479 491717 1
28829 797637 1
29727 153338 -1
34195 373096 1
35217 866814 1
39050 879581 1
42220 115350 -1
43643 514807 1
44120 296520 -1
49743 164498 1
65297 399456 -1
65515 749001 1
72368 919660 -1
74092 813117 -1
84215 27521 -1
86383 950613 1
96486 ...

output:

-1

result:

ok 1 number(s): "-1"

Test #51:

score: 17
Accepted
time: 18ms
memory: 16664kb

input:

100000
0 638674566 -1
12508 876186572 -1
20497 372512454 -1
39735 989086721 1
42208 409969479 -1
42893 503777332 1
60489 170962440 1
82608 440008381 1
89494 381753692 1
93575 891642763 1
108025 885370987 1
111638 388561056 -1
112172 675987376 1
115537 49459857 1
130744 40616828 -1
134673 798561543 -...

output:

49668

result:

ok 1 number(s): "49668"

Test #52:

score: 17
Accepted
time: 13ms
memory: 16744kb

input:

100000
0 7 -1
7 22 1
29 10 -1
39 2 1
41 42 1
83 10 -1
93 11 1
104 6 1
110 3 -1
113 24 1
137 3 1
140 5 1
145 12 -1
157 4 -1
161 8 1
169 11 -1
180 2 -1
182 2 1
184 20 1
204 5 -1
209 10 1
219 8 -1
227 49 1
276 8 1
284 5 -1
289 3 1
292 9 -1
301 2 1
303 7 -1
310 4 1
314 5 1
319 11 -1
330 3 -1
333 22 -1
3...

output:

50096

result:

ok 1 number(s): "50096"

Test #53:

score: 17
Accepted
time: 22ms
memory: 16576kb

input:

100000
0 8991 -1
8940 4643 -1
13307 5855 1
18667 1226 1
18967 1119 -1
19685 12505 -1
31590 13548 1
44868 6657 1
51479 29887 -1
81250 22949 1
103661 4918 1
107702 5071 1
112231 19683 1
131335 2735 -1
133945 809 -1
134639 4961 1
138877 10340 -1
149190 2060 -1
150350 22943 -1
172306 5545 1
177388 2763 ...

output:

49882

result:

ok 1 number(s): "49882"

Test #54:

score: 17
Accepted
time: 14ms
memory: 16680kb

input:

100000
0 20 -1
20 5 -1
25 56 1
81 3 1
84 32 -1
116 17 -1
133 9 1
142 22 -1
164 15 -1
179 9 -1
188 2 -1
190 9 -1
199 6 1
205 4 1
209 3 1
212 3 -1
215 7 1
222 5 1
227 7 1
234 20 -1
254 2 -1
256 11 -1
267 1 -1
268 27 1
295 24 1
319 10 -1
329 6 1
335 46 -1
381 8 1
389 8 1
397 25 1
422 13 -1
435 26 -1
46...

output:

-1

result:

ok 1 number(s): "-1"

Test #55:

score: 17
Accepted
time: 12ms
memory: 16744kb

input:

100000
0 4803 1
3899 3574 -1
7344 48793 -1
55391 8921 -1
63837 16717 -1
79873 1618 -1
81245 33699 -1
114388 4131 -1
118020 1040 1
118946 2407 -1
120655 8900 1
129504 39172 1
168215 13690 -1
181265 5113 -1
185817 4791 -1
190571 15711 -1
205914 11666 -1
216752 14249 -1
230317 14740 1
244285 2472 -1
24...

output:

-1

result:

ok 1 number(s): "-1"

Extra Test:

score: 0
Extra Test Passed