oj.uz

Submission #205124

# Submission time Handle Problem Language Result Execution time Memory
205124 2020-02-28T06:02:51 Z qwerty234 Aliens (IOI16_aliens) C++14
100 / 100
 689 ms 89440 KB 
#include "aliens.h"
 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define f first
#define se second
//#define int long long
#define pll pair<ll, ll>
#define pii pair<int, int>
 
 
using namespace std;
 
const int N = 3e5 + 123;
//const int N = 2e4 + 123;
const int M = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll inf = 1e16;
const ld INF = 1e17;
const ll maxR = 1e12 + 5;
 
 
struct segment {
	ll l, r, l1, r1;
	segment(ll l, ll r, ll l1, ll r1) : l(l), r(r), l1(l1), r1(r1) {};
};
 
 
struct line {
	ll b, k;
	ll cntid;
};
 
 
vector <line> lines;
 
 
ld intersect(line l1, line l2) {
	return (l1.b * 1.0 - l2.b * 1.0) / (l2.k * 1.0 - l1.k * 1.0);
}
 
 
ld val(line l, ld x) {
	return l.k * 1.0 * x + l.b;
}
 
ll vall(line l, ll x) {
	return l.k * x + l.b;
}
 
 
void addline(line a) {
	while (lines.size() > 1) {
		ld tmp = intersect(lines[lines.size() - 1], lines[lines.size() - 2]);
		if (val(lines[lines.size() - 1], tmp) > val(a, tmp))
			lines.pop_back();
		else
			break;
	}
	lines.pb(a);
}
 
 
pair<ll, ll> getmin(ll x) {
	ll L, R, M;
	pair<ll, ll> ans = {inf, inf};
	L = 0; R = lines.size() - 1;
	while (L <= R) {
		M = (L + R) / 2;
		ans = min(ans, {vall(lines[M], x), lines[M].cntid});
		if (M != lines.size() - 1)
			ans = min(ans, {vall(lines[M + 1], x), lines[M + 1].cntid});
		if (M != 0)
			ans = min(ans, {vall(lines[M - 1], x), lines[M - 1].cntid});
		if (M == lines.size() - 1) {
			R = M - 1;
			continue;
		}
		if (make_pair(vall(lines[M], x), lines[M].cntid) >= make_pair(vall(lines[M + 1], x), lines[M + 1].cntid))
			L = M + 1;
		else
			R = M - 1;
	}
	return ans;
}
 
 
ll L[N], R[N], Lto[N], Rto[N], ar[N], sz = 0;
ll cntt[N];
bool isworth[N];
vector <segment> worth;
vector <ll> byl[N];
unordered_set <ll> st[M];
ll dp[N];
 
 
 
bool cmp(segment x, segment y) {
	return x.r < y.r;
}
 
 
ll cost(ll l, ll r) {
	if (l > r)
		return 0;
	return (r - l + 1) * (r - l + 1);
}
 
 
void add(int j) {
	line tmp;
	ll addd;
	if (j == 1 || worth[j].l > worth[j - 1].r)
		addd = 0ll;
	else
		addd = cost(worth[j].l, worth[j - 1].r);		
	tmp.b = dp[j - 1] + worth[j].l * worth[j].l - addd;
	tmp.k = -2 * worth[j].l;
	tmp.cntid = cntt[j - 1];
	addline(tmp);
}
 
 
pll count(ll costt, int n) {
	lines.clear();
	dp[0] = 0;
	cntt[0] = 0;
	for (int i = 1; i <= n; i++) {
		add(i);
		pair<ld, ll> tmpp = getmin(worth[i].r + 1);
		dp[i] = costt + tmpp.f + (worth[i].r + 1) * (worth[i].r + 1);
		cntt[i] = tmpp.se + 1;
	}
	return make_pair(dp[n] - cntt[n] * costt, cntt[n]);
}
 
 
ll take_photos(int n, int m, int k, vector <int> r, vector <int> c) {
	int tmp = 0;
	for (int i = 0; i < n; i++) {
		if (c[i] >= r[i]) {
			if (st[r[i] + 1].count(c[i] + 1))
				continue;
			tmp++;
			L[tmp] = r[i] + 1;
			R[tmp] = c[i] + 1;
		} else {
			if (st[c[i] + 1].count(r[i] + 1))
				continue;
			tmp++;
			L[tmp] = c[i] + 1;
			R[tmp] = r[i] + 1;
		}
		st[L[tmp]].insert(R[tmp]);
		ar[++sz] = L[tmp];
		ar[++sz] = R[tmp];
	}
	n = tmp;
	sort(ar + 1, ar + sz + 1);
	ll t = unique(ar + 1, ar + sz + 1) - ar - 1;
	for (int i = 1; i <= n; i++) {
		Lto[i] = lower_bound(ar + 1, ar + t + 1, L[i]) - ar;		
		Rto[i] = lower_bound(ar + 1, ar + t + 1, R[i]) - ar;
		byl[Lto[i]].pb(i);
		isworth[i] = true;
	}
	ll curmax = 0;
	for (int i = 1; i <= 2 * n; i++) {
		ll localmx = 0;
		for (int to : byl[i]) {
			localmx = max(localmx, Rto[to]);
			if (Rto[to] <= curmax)
				isworth[to] = false;
		}
		for (int to : byl[i])
			if (Rto[to] < localmx)
				isworth[to] = false;
		curmax = max(curmax, localmx);
	}
	worth.pb({-1, -1, -1, -1});
	for (int i = 1; i <= n; i++) {
		if (isworth[i])
			worth.pb({L[i], R[i], Lto[i], Rto[i]});
	}
	n = worth.size() - 1;
	sort(worth.begin(), worth.end(), cmp);
	
	k = min(n, k);
	
	
	ll M, L = 0, R = maxR;
	ll ans;
	pll val1, val2; ll p1, p2;
	while (L <= R) {
//		cout << L << " " << R << endl;
		M = (L + R) / 2;
		val1 = count(M, n);
		if (val1.se < k) {
			R = M - 1;
			continue;
		}
		val2 = count(M + 1, n);
		p2 = val2.se; p1 = val1.se;
		if (val2.se > k) {
			L = M + 1;
			continue;
		}
		if (p1 == k) {
			ans = val1.f;
			break;
		}
		if (p2 == k) {
			ans = val2.f;
			break;
		}
		ll dif = (val1.f - val2.f) / (p1 - p2);
      	if ((val1.f - val2.f) % (p1 - p2) != 0)
          	return -1;
		ans = val2.f + (k - p2) * dif;
		break;
	}
	
	return ans;
}

Compilation message

aliens.cpp: In function 'std::pair<long long int, long long int> getmin(long long int)':
aliens.cpp:73:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (M != lines.size() - 1)
       ~~^~~~~~~~~~~~~~~~~~~
aliens.cpp:77:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (M == lines.size() - 1) {
       ~~^~~~~~~~~~~~~~~~~~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:219:8: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
        if ((val1.f - val2.f) % (p1 - p2) != 0)
        ^~
aliens.cpp:221:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   ans = val2.f + (k - p2) * dif;
   ^~~
aliens.cpp:194:5: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  ll ans;
     ^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 62200 KB Correct answer: answer = 4
2 Correct 51 ms 62200 KB Correct answer: answer = 4
3 Correct 49 ms 62200 KB Correct answer: answer = 4
4 Correct 49 ms 62200 KB Correct answer: answer = 12
5 Correct 55 ms 62200 KB Correct answer: answer = 52
6 Correct 49 ms 62200 KB Correct answer: answer = 210
7 Correct 48 ms 62176 KB Correct answer: answer = 88
8 Correct 49 ms 62200 KB Correct answer: answer = 7696
9 Correct 48 ms 62200 KB Correct answer: answer = 1
10 Correct 49 ms 62200 KB Correct answer: answer = 2374
11 Correct 48 ms 62200 KB Correct answer: answer = 9502
12 Correct 48 ms 62200 KB Correct answer: answer = 49
13 Correct 49 ms 62328 KB Correct answer: answer = 151
14 Correct 50 ms 62200 KB Correct answer: answer = 7550
15 Correct 49 ms 62204 KB Correct answer: answer = 7220
16 Correct 48 ms 62200 KB Correct answer: answer = 7550
17 Correct 48 ms 62200 KB Correct answer: answer = 10000
18 Correct 48 ms 62200 KB Correct answer: answer = 10000
19 Correct 48 ms 62328 KB Correct answer: answer = 624
20 Correct 50 ms 62200 KB Correct answer: answer = 10000

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 62204 KB Correct answer: answer = 1
2 Correct 48 ms 62200 KB Correct answer: answer = 4
3 Correct 49 ms 62200 KB Correct answer: answer = 1
4 Correct 49 ms 62200 KB Correct answer: answer = 5
5 Correct 51 ms 62328 KB Correct answer: answer = 41
6 Correct 49 ms 62204 KB Correct answer: answer = 71923
7 Correct 52 ms 62200 KB Correct answer: answer = 77137
8 Correct 50 ms 62328 KB Correct answer: answer = 764
9 Correct 50 ms 62328 KB Correct answer: answer = 250000
10 Correct 51 ms 62328 KB Correct answer: answer = 500
11 Correct 50 ms 62200 KB Correct answer: answer = 32
12 Correct 50 ms 62328 KB Correct answer: answer = 130050
13 Correct 51 ms 62328 KB Correct answer: answer = 5110
14 Correct 49 ms 62328 KB Correct answer: answer = 2626
15 Correct 50 ms 62328 KB Correct answer: answer = 796
16 Correct 49 ms 62328 KB Correct answer: answer = 7580
17 Correct 53 ms 62328 KB Correct answer: answer = 1904
18 Correct 49 ms 62456 KB Correct answer: answer = 996004
19 Correct 49 ms 62328 KB Correct answer: answer = 38817
20 Correct 51 ms 62328 KB Correct answer: answer = 4096
21 Correct 48 ms 62200 KB Correct answer: answer = 1
22 Correct 49 ms 62200 KB Correct answer: answer = 1
23 Correct 52 ms 62328 KB Correct answer: answer = 2040
24 Correct 50 ms 62204 KB Correct answer: answer = 2

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 62200 KB Correct answer: answer = 4
2 Correct 51 ms 62200 KB Correct answer: answer = 4
3 Correct 49 ms 62200 KB Correct answer: answer = 4
4 Correct 49 ms 62200 KB Correct answer: answer = 12
5 Correct 55 ms 62200 KB Correct answer: answer = 52
6 Correct 49 ms 62200 KB Correct answer: answer = 210
7 Correct 48 ms 62176 KB Correct answer: answer = 88
8 Correct 49 ms 62200 KB Correct answer: answer = 7696
9 Correct 48 ms 62200 KB Correct answer: answer = 1
10 Correct 49 ms 62200 KB Correct answer: answer = 2374
11 Correct 48 ms 62200 KB Correct answer: answer = 9502
12 Correct 48 ms 62200 KB Correct answer: answer = 49
13 Correct 49 ms 62328 KB Correct answer: answer = 151
14 Correct 50 ms 62200 KB Correct answer: answer = 7550
15 Correct 49 ms 62204 KB Correct answer: answer = 7220
16 Correct 48 ms 62200 KB Correct answer: answer = 7550
17 Correct 48 ms 62200 KB Correct answer: answer = 10000
18 Correct 48 ms 62200 KB Correct answer: answer = 10000
19 Correct 48 ms 62328 KB Correct answer: answer = 624
20 Correct 50 ms 62200 KB Correct answer: answer = 10000
21 Correct 49 ms 62204 KB Correct answer: answer = 1
22 Correct 48 ms 62200 KB Correct answer: answer = 4
23 Correct 49 ms 62200 KB Correct answer: answer = 1
24 Correct 49 ms 62200 KB Correct answer: answer = 5
25 Correct 51 ms 62328 KB Correct answer: answer = 41
26 Correct 49 ms 62204 KB Correct answer: answer = 71923
27 Correct 52 ms 62200 KB Correct answer: answer = 77137
28 Correct 50 ms 62328 KB Correct answer: answer = 764
29 Correct 50 ms 62328 KB Correct answer: answer = 250000
30 Correct 51 ms 62328 KB Correct answer: answer = 500
31 Correct 50 ms 62200 KB Correct answer: answer = 32
32 Correct 50 ms 62328 KB Correct answer: answer = 130050
33 Correct 51 ms 62328 KB Correct answer: answer = 5110
34 Correct 49 ms 62328 KB Correct answer: answer = 2626
35 Correct 50 ms 62328 KB Correct answer: answer = 796
36 Correct 49 ms 62328 KB Correct answer: answer = 7580
37 Correct 53 ms 62328 KB Correct answer: answer = 1904
38 Correct 49 ms 62456 KB Correct answer: answer = 996004
39 Correct 49 ms 62328 KB Correct answer: answer = 38817
40 Correct 51 ms 62328 KB Correct answer: answer = 4096
41 Correct 48 ms 62200 KB Correct answer: answer = 1
42 Correct 49 ms 62200 KB Correct answer: answer = 1
43 Correct 52 ms 62328 KB Correct answer: answer = 2040
44 Correct 50 ms 62204 KB Correct answer: answer = 2
45 Correct 49 ms 62200 KB Correct answer: answer = 4
46 Correct 50 ms 62328 KB Correct answer: answer = 9
47 Correct 49 ms 62200 KB Correct answer: answer = 9
48 Correct 49 ms 62200 KB Correct answer: answer = 21
49 Correct 49 ms 62200 KB Correct answer: answer = 71
50 Correct 50 ms 62176 KB Correct answer: answer = 77
51 Correct 50 ms 62200 KB Correct answer: answer = 400
52 Correct 49 ms 62328 KB Correct answer: answer = 996004
53 Correct 49 ms 62328 KB Correct answer: answer = 997310
54 Correct 52 ms 62328 KB Correct answer: answer = 990781
55 Correct 50 ms 62328 KB Correct answer: answer = 996545
56 Correct 50 ms 62200 KB Correct answer: answer = 484
57 Correct 49 ms 62328 KB Correct answer: answer = 484
58 Correct 49 ms 62332 KB Correct answer: answer = 63501
59 Correct 52 ms 62328 KB Correct answer: answer = 323501
60 Correct 54 ms 62328 KB Correct answer: answer = 752500
61 Correct 51 ms 62332 KB Correct answer: answer = 761480
62 Correct 49 ms 62328 KB Correct answer: answer = 758932
63 Correct 48 ms 62328 KB Correct answer: answer = 1000000
64 Correct 50 ms 62328 KB Correct answer: answer = 750500
65 Correct 48 ms 62200 KB Correct answer: answer = 1000000
66 Correct 49 ms 62328 KB Correct answer: answer = 250000
67 Correct 50 ms 62328 KB Correct answer: answer = 250000
68 Correct 48 ms 62328 KB Correct answer: answer = 1000000
69 Correct 48 ms 62328 KB Correct answer: answer = 994009
70 Correct 51 ms 62328 KB Correct answer: answer = 59315
71 Correct 49 ms 62328 KB Correct answer: answer = 25454
72 Correct 51 ms 62328 KB Correct answer: answer = 1504
73 Correct 49 ms 62328 KB Correct answer: answer = 37486
74 Correct 49 ms 62328 KB Correct answer: answer = 4284
75 Correct 48 ms 62328 KB Correct answer: answer = 158008
76 Correct 50 ms 62328 KB Correct answer: answer = 51860
77 Correct 49 ms 62328 KB Correct answer: answer = 12985

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 62200 KB Correct answer: answer = 4
2 Correct 51 ms 62200 KB Correct answer: answer = 4
3 Correct 49 ms 62200 KB Correct answer: answer = 4
4 Correct 49 ms 62200 KB Correct answer: answer = 12
5 Correct 55 ms 62200 KB Correct answer: answer = 52
6 Correct 49 ms 62200 KB Correct answer: answer = 210
7 Correct 48 ms 62176 KB Correct answer: answer = 88
8 Correct 49 ms 62200 KB Correct answer: answer = 7696
9 Correct 48 ms 62200 KB Correct answer: answer = 1
10 Correct 49 ms 62200 KB Correct answer: answer = 2374
11 Correct 48 ms 62200 KB Correct answer: answer = 9502
12 Correct 48 ms 62200 KB Correct answer: answer = 49
13 Correct 49 ms 62328 KB Correct answer: answer = 151
14 Correct 50 ms 62200 KB Correct answer: answer = 7550
15 Correct 49 ms 62204 KB Correct answer: answer = 7220
16 Correct 48 ms 62200 KB Correct answer: answer = 7550
17 Correct 48 ms 62200 KB Correct answer: answer = 10000
18 Correct 48 ms 62200 KB Correct answer: answer = 10000
19 Correct 48 ms 62328 KB Correct answer: answer = 624
20 Correct 50 ms 62200 KB Correct answer: answer = 10000
21 Correct 49 ms 62204 KB Correct answer: answer = 1
22 Correct 48 ms 62200 KB Correct answer: answer = 4
23 Correct 49 ms 62200 KB Correct answer: answer = 1
24 Correct 49 ms 62200 KB Correct answer: answer = 5
25 Correct 51 ms 62328 KB Correct answer: answer = 41
26 Correct 49 ms 62204 KB Correct answer: answer = 71923
27 Correct 52 ms 62200 KB Correct answer: answer = 77137
28 Correct 50 ms 62328 KB Correct answer: answer = 764
29 Correct 50 ms 62328 KB Correct answer: answer = 250000
30 Correct 51 ms 62328 KB Correct answer: answer = 500
31 Correct 50 ms 62200 KB Correct answer: answer = 32
32 Correct 50 ms 62328 KB Correct answer: answer = 130050
33 Correct 51 ms 62328 KB Correct answer: answer = 5110
34 Correct 49 ms 62328 KB Correct answer: answer = 2626
35 Correct 50 ms 62328 KB Correct answer: answer = 796
36 Correct 49 ms 62328 KB Correct answer: answer = 7580
37 Correct 53 ms 62328 KB Correct answer: answer = 1904
38 Correct 49 ms 62456 KB Correct answer: answer = 996004
39 Correct 49 ms 62328 KB Correct answer: answer = 38817
40 Correct 51 ms 62328 KB Correct answer: answer = 4096
41 Correct 48 ms 62200 KB Correct answer: answer = 1
42 Correct 49 ms 62200 KB Correct answer: answer = 1
43 Correct 52 ms 62328 KB Correct answer: answer = 2040
44 Correct 50 ms 62204 KB Correct answer: answer = 2
45 Correct 49 ms 62200 KB Correct answer: answer = 4
46 Correct 50 ms 62328 KB Correct answer: answer = 9
47 Correct 49 ms 62200 KB Correct answer: answer = 9
48 Correct 49 ms 62200 KB Correct answer: answer = 21
49 Correct 49 ms 62200 KB Correct answer: answer = 71
50 Correct 50 ms 62176 KB Correct answer: answer = 77
51 Correct 50 ms 62200 KB Correct answer: answer = 400
52 Correct 49 ms 62328 KB Correct answer: answer = 996004
53 Correct 49 ms 62328 KB Correct answer: answer = 997310
54 Correct 52 ms 62328 KB Correct answer: answer = 990781
55 Correct 50 ms 62328 KB Correct answer: answer = 996545
56 Correct 50 ms 62200 KB Correct answer: answer = 484
57 Correct 49 ms 62328 KB Correct answer: answer = 484
58 Correct 49 ms 62332 KB Correct answer: answer = 63501
59 Correct 52 ms 62328 KB Correct answer: answer = 323501
60 Correct 54 ms 62328 KB Correct answer: answer = 752500
61 Correct 51 ms 62332 KB Correct answer: answer = 761480
62 Correct 49 ms 62328 KB Correct answer: answer = 758932
63 Correct 48 ms 62328 KB Correct answer: answer = 1000000
64 Correct 50 ms 62328 KB Correct answer: answer = 750500
65 Correct 48 ms 62200 KB Correct answer: answer = 1000000
66 Correct 49 ms 62328 KB Correct answer: answer = 250000
67 Correct 50 ms 62328 KB Correct answer: answer = 250000
68 Correct 48 ms 62328 KB Correct answer: answer = 1000000
69 Correct 48 ms 62328 KB Correct answer: answer = 994009
70 Correct 51 ms 62328 KB Correct answer: answer = 59315
71 Correct 49 ms 62328 KB Correct answer: answer = 25454
72 Correct 51 ms 62328 KB Correct answer: answer = 1504
73 Correct 49 ms 62328 KB Correct answer: answer = 37486
74 Correct 49 ms 62328 KB Correct answer: answer = 4284
75 Correct 48 ms 62328 KB Correct answer: answer = 158008
76 Correct 50 ms 62328 KB Correct answer: answer = 51860
77 Correct 49 ms 62328 KB Correct answer: answer = 12985
78 Correct 57 ms 62972 KB Correct answer: answer = 997864126212
79 Correct 53 ms 62968 KB Correct answer: answer = 998608411647
80 Correct 53 ms 62840 KB Correct answer: answer = 995265560477
81 Correct 56 ms 63352 KB Correct answer: answer = 10125000
82 Correct 58 ms 63224 KB Correct answer: answer = 2291668
83 Correct 56 ms 62716 KB Correct answer: answer = 42388
84 Correct 58 ms 62840 KB Correct answer: answer = 10318
85 Correct 56 ms 62712 KB Correct answer: answer = 3416
86 Correct 55 ms 63224 KB Correct answer: answer = 331708193881
87 Correct 65 ms 63224 KB Correct answer: answer = 2861193756
88 Correct 67 ms 63352 KB Correct answer: answer = 114646930
89 Correct 64 ms 63328 KB Correct answer: answer = 9280921
90 Correct 69 ms 63224 KB Correct answer: answer = 999984053400
91 Correct 70 ms 63224 KB Correct answer: answer = 750935949134
92 Correct 52 ms 62968 KB Correct answer: answer = 1000000000000
93 Correct 53 ms 62840 KB Correct answer: answer = 998762383161
94 Correct 64 ms 63224 KB Correct answer: answer = 23017412908
95 Correct 52 ms 62968 KB Correct answer: answer = 728143410622
96 Correct 49 ms 62328 KB Correct answer: answer = 2
97 Correct 59 ms 63224 KB Correct answer: answer = 1824916
98 Correct 74 ms 63224 KB Correct answer: answer = 10680029
99 Correct 66 ms 63224 KB Correct answer: answer = 18351700
100 Correct 53 ms 63224 KB Correct answer: answer = 16040026
101 Correct 52 ms 62840 KB Correct answer: answer = 253968628325
102 Correct 56 ms 62712 KB Correct answer: answer = 10267
103 Correct 71 ms 63224 KB Correct answer: answer = 2582408
104 Correct 52 ms 62840 KB Correct answer: answer = 78024964781
105 Correct 53 ms 62896 KB Correct answer: answer = 9866346457
106 Correct 56 ms 62968 KB Correct answer: answer = 3327720949
107 Correct 54 ms 62968 KB Correct answer: answer = 86064128360
108 Correct 55 ms 63096 KB Correct answer: answer = 12698259150
109 Correct 72 ms 63224 KB Correct answer: answer = 1185259288

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 62200 KB Correct answer: answer = 4
2 Correct 51 ms 62200 KB Correct answer: answer = 4
3 Correct 49 ms 62200 KB Correct answer: answer = 4
4 Correct 49 ms 62200 KB Correct answer: answer = 12
5 Correct 55 ms 62200 KB Correct answer: answer = 52
6 Correct 49 ms 62200 KB Correct answer: answer = 210
7 Correct 48 ms 62176 KB Correct answer: answer = 88
8 Correct 49 ms 62200 KB Correct answer: answer = 7696
9 Correct 48 ms 62200 KB Correct answer: answer = 1
10 Correct 49 ms 62200 KB Correct answer: answer = 2374
11 Correct 48 ms 62200 KB Correct answer: answer = 9502
12 Correct 48 ms 62200 KB Correct answer: answer = 49
13 Correct 49 ms 62328 KB Correct answer: answer = 151
14 Correct 50 ms 62200 KB Correct answer: answer = 7550
15 Correct 49 ms 62204 KB Correct answer: answer = 7220
16 Correct 48 ms 62200 KB Correct answer: answer = 7550
17 Correct 48 ms 62200 KB Correct answer: answer = 10000
18 Correct 48 ms 62200 KB Correct answer: answer = 10000
19 Correct 48 ms 62328 KB Correct answer: answer = 624
20 Correct 50 ms 62200 KB Correct answer: answer = 10000
21 Correct 49 ms 62204 KB Correct answer: answer = 1
22 Correct 48 ms 62200 KB Correct answer: answer = 4
23 Correct 49 ms 62200 KB Correct answer: answer = 1
24 Correct 49 ms 62200 KB Correct answer: answer = 5
25 Correct 51 ms 62328 KB Correct answer: answer = 41
26 Correct 49 ms 62204 KB Correct answer: answer = 71923
27 Correct 52 ms 62200 KB Correct answer: answer = 77137
28 Correct 50 ms 62328 KB Correct answer: answer = 764
29 Correct 50 ms 62328 KB Correct answer: answer = 250000
30 Correct 51 ms 62328 KB Correct answer: answer = 500
31 Correct 50 ms 62200 KB Correct answer: answer = 32
32 Correct 50 ms 62328 KB Correct answer: answer = 130050
33 Correct 51 ms 62328 KB Correct answer: answer = 5110
34 Correct 49 ms 62328 KB Correct answer: answer = 2626
35 Correct 50 ms 62328 KB Correct answer: answer = 796
36 Correct 49 ms 62328 KB Correct answer: answer = 7580
37 Correct 53 ms 62328 KB Correct answer: answer = 1904
38 Correct 49 ms 62456 KB Correct answer: answer = 996004
39 Correct 49 ms 62328 KB Correct answer: answer = 38817
40 Correct 51 ms 62328 KB Correct answer: answer = 4096
41 Correct 48 ms 62200 KB Correct answer: answer = 1
42 Correct 49 ms 62200 KB Correct answer: answer = 1
43 Correct 52 ms 62328 KB Correct answer: answer = 2040
44 Correct 50 ms 62204 KB Correct answer: answer = 2
45 Correct 49 ms 62200 KB Correct answer: answer = 4
46 Correct 50 ms 62328 KB Correct answer: answer = 9
47 Correct 49 ms 62200 KB Correct answer: answer = 9
48 Correct 49 ms 62200 KB Correct answer: answer = 21
49 Correct 49 ms 62200 KB Correct answer: answer = 71
50 Correct 50 ms 62176 KB Correct answer: answer = 77
51 Correct 50 ms 62200 KB Correct answer: answer = 400
52 Correct 49 ms 62328 KB Correct answer: answer = 996004
53 Correct 49 ms 62328 KB Correct answer: answer = 997310
54 Correct 52 ms 62328 KB Correct answer: answer = 990781
55 Correct 50 ms 62328 KB Correct answer: answer = 996545
56 Correct 50 ms 62200 KB Correct answer: answer = 484
57 Correct 49 ms 62328 KB Correct answer: answer = 484
58 Correct 49 ms 62332 KB Correct answer: answer = 63501
59 Correct 52 ms 62328 KB Correct answer: answer = 323501
60 Correct 54 ms 62328 KB Correct answer: answer = 752500
61 Correct 51 ms 62332 KB Correct answer: answer = 761480
62 Correct 49 ms 62328 KB Correct answer: answer = 758932
63 Correct 48 ms 62328 KB Correct answer: answer = 1000000
64 Correct 50 ms 62328 KB Correct answer: answer = 750500
65 Correct 48 ms 62200 KB Correct answer: answer = 1000000
66 Correct 49 ms 62328 KB Correct answer: answer = 250000
67 Correct 50 ms 62328 KB Correct answer: answer = 250000
68 Correct 48 ms 62328 KB Correct answer: answer = 1000000
69 Correct 48 ms 62328 KB Correct answer: answer = 994009
70 Correct 51 ms 62328 KB Correct answer: answer = 59315
71 Correct 49 ms 62328 KB Correct answer: answer = 25454
72 Correct 51 ms 62328 KB Correct answer: answer = 1504
73 Correct 49 ms 62328 KB Correct answer: answer = 37486
74 Correct 49 ms 62328 KB Correct answer: answer = 4284
75 Correct 48 ms 62328 KB Correct answer: answer = 158008
76 Correct 50 ms 62328 KB Correct answer: answer = 51860
77 Correct 49 ms 62328 KB Correct answer: answer = 12985
78 Correct 57 ms 62972 KB Correct answer: answer = 997864126212
79 Correct 53 ms 62968 KB Correct answer: answer = 998608411647
80 Correct 53 ms 62840 KB Correct answer: answer = 995265560477
81 Correct 56 ms 63352 KB Correct answer: answer = 10125000
82 Correct 58 ms 63224 KB Correct answer: answer = 2291668
83 Correct 56 ms 62716 KB Correct answer: answer = 42388
84 Correct 58 ms 62840 KB Correct answer: answer = 10318
85 Correct 56 ms 62712 KB Correct answer: answer = 3416
86 Correct 55 ms 63224 KB Correct answer: answer = 331708193881
87 Correct 65 ms 63224 KB Correct answer: answer = 2861193756
88 Correct 67 ms 63352 KB Correct answer: answer = 114646930
89 Correct 64 ms 63328 KB Correct answer: answer = 9280921
90 Correct 69 ms 63224 KB Correct answer: answer = 999984053400
91 Correct 70 ms 63224 KB Correct answer: answer = 750935949134
92 Correct 52 ms 62968 KB Correct answer: answer = 1000000000000
93 Correct 53 ms 62840 KB Correct answer: answer = 998762383161
94 Correct 64 ms 63224 KB Correct answer: answer = 23017412908
95 Correct 52 ms 62968 KB Correct answer: answer = 728143410622
96 Correct 49 ms 62328 KB Correct answer: answer = 2
97 Correct 59 ms 63224 KB Correct answer: answer = 1824916
98 Correct 74 ms 63224 KB Correct answer: answer = 10680029
99 Correct 66 ms 63224 KB Correct answer: answer = 18351700
100 Correct 53 ms 63224 KB Correct answer: answer = 16040026
101 Correct 52 ms 62840 KB Correct answer: answer = 253968628325
102 Correct 56 ms 62712 KB Correct answer: answer = 10267
103 Correct 71 ms 63224 KB Correct answer: answer = 2582408
104 Correct 52 ms 62840 KB Correct answer: answer = 78024964781
105 Correct 53 ms 62896 KB Correct answer: answer = 9866346457
106 Correct 56 ms 62968 KB Correct answer: answer = 3327720949
107 Correct 54 ms 62968 KB Correct answer: answer = 86064128360
108 Correct 55 ms 63096 KB Correct answer: answer = 12698259150
109 Correct 72 ms 63224 KB Correct answer: answer = 1185259288
110 Correct 121 ms 70812 KB Correct answer: answer = 999889968863
111 Correct 116 ms 70776 KB Correct answer: answer = 999861384931
112 Correct 117 ms 70776 KB Correct answer: answer = 999811809929
113 Correct 116 ms 70648 KB Correct answer: answer = 999869756441
114 Correct 143 ms 74476 KB Correct answer: answer = 1700000000
115 Correct 216 ms 75500 KB Correct answer: answer = 131666670
116 Correct 79 ms 66408 KB Correct answer: answer = 89478486
117 Correct 107 ms 66540 KB Correct answer: answer = 4971040
118 Correct 110 ms 66540 KB Correct answer: answer = 2711494
119 Correct 249 ms 75624 KB Correct answer: answer = 25252530
120 Correct 237 ms 75628 KB Correct answer: answer = 62500000
121 Correct 141 ms 73068 KB Correct answer: answer = 333175097780
122 Correct 200 ms 73068 KB Correct answer: answer = 33121180179
123 Correct 255 ms 73068 KB Correct answer: answer = 9802314015
124 Correct 251 ms 75980 KB Correct answer: answer = 32567551
125 Correct 263 ms 75756 KB Correct answer: answer = 997525000000
126 Correct 259 ms 73064 KB Correct answer: answer = 752723538884
127 Correct 85 ms 70648 KB Correct answer: answer = 1000000000000
128 Correct 116 ms 70648 KB Correct answer: answer = 999978000121
129 Correct 120 ms 70648 KB Correct answer: answer = 745986144735
130 Correct 60 ms 63352 KB Correct answer: answer = 2
131 Correct 177 ms 75444 KB Correct answer: answer = 277966670
132 Correct 118 ms 73196 KB Correct answer: answer = 2500900082
133 Correct 107 ms 70260 KB Correct answer: answer = 301248349636
134 Correct 163 ms 68328 KB Correct answer: answer = 14118891
135 Correct 111 ms 70136 KB Correct answer: answer = 14384977265
136 Correct 119 ms 70264 KB Correct answer: answer = 3681368330
137 Correct 120 ms 70264 KB Correct answer: answer = 2720316816

Subtask #6
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 62200 KB Correct answer: answer = 4
2 Correct 51 ms 62200 KB Correct answer: answer = 4
3 Correct 49 ms 62200 KB Correct answer: answer = 4
4 Correct 49 ms 62200 KB Correct answer: answer = 12
5 Correct 55 ms 62200 KB Correct answer: answer = 52
6 Correct 49 ms 62200 KB Correct answer: answer = 210
7 Correct 48 ms 62176 KB Correct answer: answer = 88
8 Correct 49 ms 62200 KB Correct answer: answer = 7696
9 Correct 48 ms 62200 KB Correct answer: answer = 1
10 Correct 49 ms 62200 KB Correct answer: answer = 2374
11 Correct 48 ms 62200 KB Correct answer: answer = 9502
12 Correct 48 ms 62200 KB Correct answer: answer = 49
13 Correct 49 ms 62328 KB Correct answer: answer = 151
14 Correct 50 ms 62200 KB Correct answer: answer = 7550
15 Correct 49 ms 62204 KB Correct answer: answer = 7220
16 Correct 48 ms 62200 KB Correct answer: answer = 7550
17 Correct 48 ms 62200 KB Correct answer: answer = 10000
18 Correct 48 ms 62200 KB Correct answer: answer = 10000
19 Correct 48 ms 62328 KB Correct answer: answer = 624
20 Correct 50 ms 62200 KB Correct answer: answer = 10000
21 Correct 49 ms 62204 KB Correct answer: answer = 1
22 Correct 48 ms 62200 KB Correct answer: answer = 4
23 Correct 49 ms 62200 KB Correct answer: answer = 1
24 Correct 49 ms 62200 KB Correct answer: answer = 5
25 Correct 51 ms 62328 KB Correct answer: answer = 41
26 Correct 49 ms 62204 KB Correct answer: answer = 71923
27 Correct 52 ms 62200 KB Correct answer: answer = 77137
28 Correct 50 ms 62328 KB Correct answer: answer = 764
29 Correct 50 ms 62328 KB Correct answer: answer = 250000
30 Correct 51 ms 62328 KB Correct answer: answer = 500
31 Correct 50 ms 62200 KB Correct answer: answer = 32
32 Correct 50 ms 62328 KB Correct answer: answer = 130050
33 Correct 51 ms 62328 KB Correct answer: answer = 5110
34 Correct 49 ms 62328 KB Correct answer: answer = 2626
35 Correct 50 ms 62328 KB Correct answer: answer = 796
36 Correct 49 ms 62328 KB Correct answer: answer = 7580
37 Correct 53 ms 62328 KB Correct answer: answer = 1904
38 Correct 49 ms 62456 KB Correct answer: answer = 996004
39 Correct 49 ms 62328 KB Correct answer: answer = 38817
40 Correct 51 ms 62328 KB Correct answer: answer = 4096
41 Correct 48 ms 62200 KB Correct answer: answer = 1
42 Correct 49 ms 62200 KB Correct answer: answer = 1
43 Correct 52 ms 62328 KB Correct answer: answer = 2040
44 Correct 50 ms 62204 KB Correct answer: answer = 2
45 Correct 49 ms 62200 KB Correct answer: answer = 4
46 Correct 50 ms 62328 KB Correct answer: answer = 9
47 Correct 49 ms 62200 KB Correct answer: answer = 9
48 Correct 49 ms 62200 KB Correct answer: answer = 21
49 Correct 49 ms 62200 KB Correct answer: answer = 71
50 Correct 50 ms 62176 KB Correct answer: answer = 77
51 Correct 50 ms 62200 KB Correct answer: answer = 400
52 Correct 49 ms 62328 KB Correct answer: answer = 996004
53 Correct 49 ms 62328 KB Correct answer: answer = 997310
54 Correct 52 ms 62328 KB Correct answer: answer = 990781
55 Correct 50 ms 62328 KB Correct answer: answer = 996545
56 Correct 50 ms 62200 KB Correct answer: answer = 484
57 Correct 49 ms 62328 KB Correct answer: answer = 484
58 Correct 49 ms 62332 KB Correct answer: answer = 63501
59 Correct 52 ms 62328 KB Correct answer: answer = 323501
60 Correct 54 ms 62328 KB Correct answer: answer = 752500
61 Correct 51 ms 62332 KB Correct answer: answer = 761480
62 Correct 49 ms 62328 KB Correct answer: answer = 758932
63 Correct 48 ms 62328 KB Correct answer: answer = 1000000
64 Correct 50 ms 62328 KB Correct answer: answer = 750500
65 Correct 48 ms 62200 KB Correct answer: answer = 1000000
66 Correct 49 ms 62328 KB Correct answer: answer = 250000
67 Correct 50 ms 62328 KB Correct answer: answer = 250000
68 Correct 48 ms 62328 KB Correct answer: answer = 1000000
69 Correct 48 ms 62328 KB Correct answer: answer = 994009
70 Correct 51 ms 62328 KB Correct answer: answer = 59315
71 Correct 49 ms 62328 KB Correct answer: answer = 25454
72 Correct 51 ms 62328 KB Correct answer: answer = 1504
73 Correct 49 ms 62328 KB Correct answer: answer = 37486
74 Correct 49 ms 62328 KB Correct answer: answer = 4284
75 Correct 48 ms 62328 KB Correct answer: answer = 158008
76 Correct 50 ms 62328 KB Correct answer: answer = 51860
77 Correct 49 ms 62328 KB Correct answer: answer = 12985
78 Correct 57 ms 62972 KB Correct answer: answer = 997864126212
79 Correct 53 ms 62968 KB Correct answer: answer = 998608411647
80 Correct 53 ms 62840 KB Correct answer: answer = 995265560477
81 Correct 56 ms 63352 KB Correct answer: answer = 10125000
82 Correct 58 ms 63224 KB Correct answer: answer = 2291668
83 Correct 56 ms 62716 KB Correct answer: answer = 42388
84 Correct 58 ms 62840 KB Correct answer: answer = 10318
85 Correct 56 ms 62712 KB Correct answer: answer = 3416
86 Correct 55 ms 63224 KB Correct answer: answer = 331708193881
87 Correct 65 ms 63224 KB Correct answer: answer = 2861193756
88 Correct 67 ms 63352 KB Correct answer: answer = 114646930
89 Correct 64 ms 63328 KB Correct answer: answer = 9280921
90 Correct 69 ms 63224 KB Correct answer: answer = 999984053400
91 Correct 70 ms 63224 KB Correct answer: answer = 750935949134
92 Correct 52 ms 62968 KB Correct answer: answer = 1000000000000
93 Correct 53 ms 62840 KB Correct answer: answer = 998762383161
94 Correct 64 ms 63224 KB Correct answer: answer = 23017412908
95 Correct 52 ms 62968 KB Correct answer: answer = 728143410622
96 Correct 49 ms 62328 KB Correct answer: answer = 2
97 Correct 59 ms 63224 KB Correct answer: answer = 1824916
98 Correct 74 ms 63224 KB Correct answer: answer = 10680029
99 Correct 66 ms 63224 KB Correct answer: answer = 18351700
100 Correct 53 ms 63224 KB Correct answer: answer = 16040026
101 Correct 52 ms 62840 KB Correct answer: answer = 253968628325
102 Correct 56 ms 62712 KB Correct answer: answer = 10267
103 Correct 71 ms 63224 KB Correct answer: answer = 2582408
104 Correct 52 ms 62840 KB Correct answer: answer = 78024964781
105 Correct 53 ms 62896 KB Correct answer: answer = 9866346457
106 Correct 56 ms 62968 KB Correct answer: answer = 3327720949
107 Correct 54 ms 62968 KB Correct answer: answer = 86064128360
108 Correct 55 ms 63096 KB Correct answer: answer = 12698259150
109 Correct 72 ms 63224 KB Correct answer: answer = 1185259288
110 Correct 121 ms 70812 KB Correct answer: answer = 999889968863
111 Correct 116 ms 70776 KB Correct answer: answer = 999861384931
112 Correct 117 ms 70776 KB Correct answer: answer = 999811809929
113 Correct 116 ms 70648 KB Correct answer: answer = 999869756441
114 Correct 143 ms 74476 KB Correct answer: answer = 1700000000
115 Correct 216 ms 75500 KB Correct answer: answer = 131666670
116 Correct 79 ms 66408 KB Correct answer: answer = 89478486
117 Correct 107 ms 66540 KB Correct answer: answer = 4971040
118 Correct 110 ms 66540 KB Correct answer: answer = 2711494
119 Correct 249 ms 75624 KB Correct answer: answer = 25252530
120 Correct 237 ms 75628 KB Correct answer: answer = 62500000
121 Correct 141 ms 73068 KB Correct answer: answer = 333175097780
122 Correct 200 ms 73068 KB Correct answer: answer = 33121180179
123 Correct 255 ms 73068 KB Correct answer: answer = 9802314015
124 Correct 251 ms 75980 KB Correct answer: answer = 32567551
125 Correct 263 ms 75756 KB Correct answer: answer = 997525000000
126 Correct 259 ms 73064 KB Correct answer: answer = 752723538884
127 Correct 85 ms 70648 KB Correct answer: answer = 1000000000000
128 Correct 116 ms 70648 KB Correct answer: answer = 999978000121
129 Correct 120 ms 70648 KB Correct answer: answer = 745986144735
130 Correct 60 ms 63352 KB Correct answer: answer = 2
131 Correct 177 ms 75444 KB Correct answer: answer = 277966670
132 Correct 118 ms 73196 KB Correct answer: answer = 2500900082
133 Correct 107 ms 70260 KB Correct answer: answer = 301248349636
134 Correct 163 ms 68328 KB Correct answer: answer = 14118891
135 Correct 111 ms 70136 KB Correct answer: answer = 14384977265
136 Correct 119 ms 70264 KB Correct answer: answer = 3681368330
137 Correct 120 ms 70264 KB Correct answer: answer = 2720316816
138 Correct 196 ms 78968 KB Correct answer: answer = 999976000144
139 Correct 206 ms 78968 KB Correct answer: answer = 999856102410
140 Correct 196 ms 78968 KB Correct answer: answer = 999958401531
141 Correct 192 ms 78968 KB Correct answer: answer = 999769649944
142 Correct 199 ms 78968 KB Correct answer: answer = 999874525918
143 Correct 251 ms 86496 KB Correct answer: answer = 6050000000
144 Correct 316 ms 86880 KB Correct answer: answer = 1112500000
145 Correct 104 ms 77548 KB Correct answer: answer = 4294967296
146 Correct 346 ms 79324 KB Correct answer: answer = 87652406
147 Correct 347 ms 79460 KB Correct answer: answer = 6297664
148 Correct 376 ms 79460 KB Correct answer: answer = 196612
149 Correct 641 ms 89316 KB Correct answer: answer = 15015100
150 Correct 515 ms 89312 KB Correct answer: answer = 25000000
151 Correct 235 ms 83172 KB Correct answer: answer = 333230209550
152 Correct 581 ms 83556 KB Correct answer: answer = 917123769
153 Correct 677 ms 88492 KB Correct answer: answer = 95162
154 Correct 431 ms 89148 KB Correct answer: answer = 382616191
155 Correct 591 ms 89312 KB Correct answer: answer = 990033333400
156 Correct 689 ms 89440 KB Correct answer: answer = 990000100000
157 Correct 600 ms 85604 KB Correct answer: answer = 749998188180
158 Correct 122 ms 79256 KB Correct answer: answer = 1000000000000
159 Correct 184 ms 78712 KB Correct answer: answer = 999988000036
160 Correct 208 ms 78840 KB Correct answer: answer = 744929274393
161 Correct 69 ms 64120 KB Correct answer: answer = 2
162 Correct 680 ms 89312 KB Correct answer: answer = 1300024
163 Correct 252 ms 86368 KB Correct answer: answer = 5000700010
164 Correct 195 ms 77940 KB Correct answer: answer = 354997100800
165 Correct 366 ms 75500 KB Correct answer: answer = 257000
166 Correct 440 ms 76012 KB Correct answer: answer = 3765323
167 Correct 379 ms 75756 KB Correct answer: answer = 1525903
168 Correct 187 ms 77944 KB Correct answer: answer = 67618137730
169 Correct 207 ms 78328 KB Correct answer: answer = 12656680171
170 Correct 206 ms 78072 KB Correct answer: answer = 579831736
171 Correct 351 ms 79468 KB Correct answer: answer = 23605611
172 Correct 219 ms 79096 KB Correct answer: answer = 7052481200
173 Correct 239 ms 79984 KB Correct answer: answer = 1314039500
174 Correct 282 ms 80976 KB Correct answer: answer = 302484000
175 Correct 528 ms 83432 KB Correct answer: answer = 52348480