Submission #1101131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101131		rainboy	Nile (IOI24_nile)	C++17	100 / 100	240 ms	30936 KiB

nile

#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
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15
• Subtask 7: 18 / 18