oj.uz

Submission #1101131

# Submission time Handle Problem Language Result Execution time Memory
1101131 2024-10-15T15:21:45 Z rainboy Nile (IOI24_nile) C++17
100 / 100
 240 ms 30936 KB 
#include "nile.h"
#include <cstring>

using namespace std;

typedef vector<int> vi;
typedef vector<long long> vl;

const int N = 100000, N_ = 1 << 17, M = N - 1 + N - 2, Q = 100000;	/* N_ = pow2(ceil(log2(N))) */
const long long INF = 0x3f3f3f3f3f3f3f3f;

long long min(long long a, long long b) { return a < b ? a : b; }

unsigned int Z = 12345;

int rand_() {
	return (Z *= 3) >> 1;
}

int xx[N], aa[N], bb[N], ii[N];
int dd[Q], gg[Q];
int cc[M], hh[M];

int *ww;

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
		while (j < k)
			if (ww[ii[j]] == ww[i_])
				j++;
			else if (ww[ii[j]] < ww[i_]) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		sort(ii, l, i);
		l = k;
	}
}

long long dp[N + 1];
long long st[N_ * 2][3][3]; int n_;

void pul(int i) {
	int l = i << 1, r = l | 1;
	memset(st[i], 0x3f, sizeof st[i]);
	for (int a = 0; a < 3; a++)
		for (int b = 0; b < 3; b++)
			for (int c = 0; c < 3; c++)
				st[i][a][c] = min(st[i][a][c], st[l][a][b] + st[r][b][c]);
}

void build(int n) {
	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	for (int i = 0; i < n_; i++) {
		memset(st[n_ + i], 0x3f, sizeof st[n_ + i]);
		if (i < n)
			st[n_ + i][0][0] = aa[i], st[n_ + i][2][1] = aa[i], st[n_ + i][1][0] = bb[i];
		else
			st[n_ + i][0][0] = 0, st[n_ + i][1][1] = 0;
	}
	for (int i = n_ - 1; i > 0; i--)
		pul(i);
}

void update(int i, int b, int w) {
	i += n_;
	st[i][0][b] = w;
	while (i > 1)
		pul(i >>= 1);
}

vl calculate_costs(vi xx_, vi aa_, vi bb_, vi dd_) {
	int n = xx_.size(), q = dd_.size();
	for (int i = 0; i < n; i++)
		xx[i] = xx_[i], aa[i] = aa_[i], bb[i] = bb_[i];
	if (n == 1) {
		vl ans(q, 0);
		for (int h = 0; h < q; h++)
			ans[h] = aa[0];
		return ans;
	}
	for (int g = 0; g < q; g++)
		dd[g] = dd_[g];
	for (int i = 0; i < n; i++)
		ii[i] = i;
	ww = xx, sort(ii, 0, n);
	for (int i = 0; i < n; i++)
		xx_[i] = xx[ii[i]], aa_[i] = aa[ii[i]], bb_[i] = bb[ii[i]];
	for (int i = 0; i < n; i++)
		xx[i] = xx_[i], aa[i] = aa_[i], bb[i] = bb_[i];
	int m = n - 1 + n - 2;
	for (int i = 0; i + 1 < n; i++)
		cc[i] = xx[i + 1] - xx[i];
	for (int i = 0; i + 2 < n; i++)
		cc[n - 1 + i] = xx[i + 2] - xx[i];
	for (int h = 0; h < m; h++)
		hh[h] = h;
	ww = cc, sort(hh, 0, m);
	for (int g = 0; g < q; g++)
		gg[g] = g;
	ww = dd, sort(gg, 0, q);
	build(n);
	vl ans(q, 0);
	for (int g = 0, h = 0; g < q; g++) {
		int g_ = gg[g], d = dd[g_], h_;
		while (h < m && cc[h_ = hh[h]] <= d) {
			if (h_ + 1 < n)
				update(h_, 1, bb[h_]);
			else
				update(h_ - (n - 1), 2, bb[h_ - (n - 1)]);
			h++;
		}
		ans[g_] = st[1][0][0];
	}
	return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4436 KB Output is correct

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 28372 KB Output is correct
2 Correct 155 ms 28336 KB Output is correct
3 Correct 152 ms 28232 KB Output is correct
4 Correct 149 ms 28240 KB Output is correct
5 Correct 165 ms 28232 KB Output is correct
6 Correct 165 ms 28216 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 26980 KB Output is correct
2 Correct 165 ms 27220 KB Output is correct
3 Correct 192 ms 27220 KB Output is correct
4 Correct 177 ms 27208 KB Output is correct
5 Correct 161 ms 27216 KB Output is correct
6 Correct 189 ms 27224 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 4 ms 4944 KB Output is correct
8 Correct 4 ms 4944 KB Output is correct
9 Correct 4 ms 4924 KB Output is correct
10 Correct 4 ms 4804 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 4 ms 4944 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 162 ms 28372 KB Output is correct
8 Correct 155 ms 28336 KB Output is correct
9 Correct 152 ms 28232 KB Output is correct
10 Correct 149 ms 28240 KB Output is correct
11 Correct 165 ms 28232 KB Output is correct
12 Correct 165 ms 28216 KB Output is correct
13 Correct 159 ms 26980 KB Output is correct
14 Correct 165 ms 27220 KB Output is correct
15 Correct 192 ms 27220 KB Output is correct
16 Correct 177 ms 27208 KB Output is correct
17 Correct 161 ms 27216 KB Output is correct
18 Correct 189 ms 27224 KB Output is correct
19 Correct 4 ms 4944 KB Output is correct
20 Correct 4 ms 4944 KB Output is correct
21 Correct 4 ms 4924 KB Output is correct
22 Correct 4 ms 4804 KB Output is correct
23 Correct 3 ms 4948 KB Output is correct
24 Correct 4 ms 4944 KB Output is correct
25 Correct 172 ms 28504 KB Output is correct
26 Correct 166 ms 28764 KB Output is correct
27 Correct 177 ms 28748 KB Output is correct
28 Correct 184 ms 28744 KB Output is correct
29 Correct 185 ms 28488 KB Output is correct
30 Correct 186 ms 28740 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 26980 KB Output is correct
2 Correct 165 ms 27220 KB Output is correct
3 Correct 192 ms 27220 KB Output is correct
4 Correct 177 ms 27208 KB Output is correct
5 Correct 161 ms 27216 KB Output is correct
6 Correct 189 ms 27224 KB Output is correct
7 Correct 188 ms 29000 KB Output is correct
8 Correct 192 ms 29256 KB Output is correct
9 Correct 201 ms 29256 KB Output is correct
10 Correct 203 ms 29256 KB Output is correct
11 Correct 203 ms 29256 KB Output is correct
12 Correct 204 ms 29256 KB Output is correct
13 Correct 207 ms 29248 KB Output is correct
14 Correct 193 ms 29000 KB Output is correct
15 Correct 228 ms 29380 KB Output is correct

Subtask #7
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4436 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 3 ms 4944 KB Output is correct
4 Correct 4 ms 4948 KB Output is correct
5 Correct 3 ms 4944 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 162 ms 28372 KB Output is correct
9 Correct 155 ms 28336 KB Output is correct
10 Correct 152 ms 28232 KB Output is correct
11 Correct 149 ms 28240 KB Output is correct
12 Correct 165 ms 28232 KB Output is correct
13 Correct 165 ms 28216 KB Output is correct
14 Correct 159 ms 26980 KB Output is correct
15 Correct 165 ms 27220 KB Output is correct
16 Correct 192 ms 27220 KB Output is correct
17 Correct 177 ms 27208 KB Output is correct
18 Correct 161 ms 27216 KB Output is correct
19 Correct 189 ms 27224 KB Output is correct
20 Correct 4 ms 4944 KB Output is correct
21 Correct 4 ms 4944 KB Output is correct
22 Correct 4 ms 4924 KB Output is correct
23 Correct 4 ms 4804 KB Output is correct
24 Correct 3 ms 4948 KB Output is correct
25 Correct 4 ms 4944 KB Output is correct
26 Correct 172 ms 28504 KB Output is correct
27 Correct 166 ms 28764 KB Output is correct
28 Correct 177 ms 28748 KB Output is correct
29 Correct 184 ms 28744 KB Output is correct
30 Correct 185 ms 28488 KB Output is correct
31 Correct 186 ms 28740 KB Output is correct
32 Correct 188 ms 29000 KB Output is correct
33 Correct 192 ms 29256 KB Output is correct
34 Correct 201 ms 29256 KB Output is correct
35 Correct 203 ms 29256 KB Output is correct
36 Correct 203 ms 29256 KB Output is correct
37 Correct 204 ms 29256 KB Output is correct
38 Correct 207 ms 29248 KB Output is correct
39 Correct 193 ms 29000 KB Output is correct
40 Correct 228 ms 29380 KB Output is correct
41 Correct 198 ms 30724 KB Output is correct
42 Correct 207 ms 30936 KB Output is correct
43 Correct 221 ms 30768 KB Output is correct
44 Correct 213 ms 30920 KB Output is correct
45 Correct 240 ms 30924 KB Output is correct
46 Correct 209 ms 30792 KB Output is correct
47 Correct 225 ms 30792 KB Output is correct
48 Correct 196 ms 30536 KB Output is correct
49 Correct 234 ms 30792 KB Output is correct