Submission #1106477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106477		Octagons	Nile (IOI24_nile)	C++17	100 / 100	263 ms	32700 KiB

nile

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct node {
	ll a[3][3];
} t[(1 << 19)];
int n;
ll cd, dp[20];
vector<array<ll, 3>> v;

bool ok(int i, int j) {
	if (i < 0 || j >= n)return false;
	return (v[j][0] - v[i][0] <= cd);
}

ll pr(int i, int j) {
	return v[i][1] + v[j][1];
}

ll clc(int l, int r) {
	if (l == r)return v[l][2];
	int sz = r-l+1;
	dp[sz] = 0;
	for (int j = sz-1, cur = r; j >= 0; j--, cur--) {
		dp[j] = v[cur][2] + dp[j+1];
		if (j+1 < sz && ok(cur, cur+1)) {
			dp[j] = min(dp[j], pr(cur, cur+1) + dp[j+2]);
		}
		if (j+2 < sz && ok(cur, cur+2)) {
			dp[j] = min(dp[j], dp[j+3] + pr(cur, cur+2) + v[cur+1][2]);
		}
	}
	return dp[0];
}

void calc(int l, int r, int x) {
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (i + j > r - l + 1) {
				t[x].a[i][j] = 1e18;
				continue;
			}
			t[x].a[i][j] = clc(l + i, r - j);
		}
	}
}

node merge(node &lef, node &rig, int m) {
	node ret;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			ret.a[i][j] = lef.a[i][0] + rig.a[0][j];
			if (ok(m, m+1)) {
				ret.a[i][j] = min(ret.a[i][j], lef.a[i][1] + rig.a[1][j] + pr(m, m+1));
			}
			if (ok(m, m+2)) {
				ret.a[i][j] = min(ret.a[i][j], lef.a[i][1] + rig.a[2][j] + pr(m, m+2) + v[m+1][2]);
			}
			if (ok(m-1, m+1)) {
				ret.a[i][j] = min(ret.a[i][j], lef.a[i][2] + rig.a[1][j] + pr(m-1, m+1) + v[m][2]);
			}
		}
	}
	return ret;
}

void build(int l, int r, int x) {
	if (l == r) {
		calc(l, r, x);
		return;
	}
	int m = (l + r) >> 1;
	build(l, m, x * 2 + 1);
	build(m+1, r, x * 2 + 2);
	if (min(m-l+1, r-m) < 4) {
		calc(l, r, x);
		return;
	}
	t[x] = merge(t[x*2+1], t[x*2+2], m);
}

void upd(int l, int r, int x, int i) {
	if (l == r)return;
	int m = (l + r) >> 1;
	if (i <= m) {
		upd(l, m, x * 2 + 1, i);
	} else {
		upd(m+1, r, x * 2 + 2, i);
	}
	if (min(m-l+1, r-m) < 4) {
		calc(l, r, x);
		return;
	}
	t[x] = merge(t[x*2+1], t[x*2+2], m);
}

void init() {
	cd = 0;
	build(0, n - 1, 0);
}

vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
	int q = E.size();
	vector<ll> ans(q);
	n = W.size();
	vector<pair<int, int>> qr(q);
	for (int i = 0; i < q; i++) {
		qr[i] = {E[i], i};
	}
	v.resize(n);
	for (int i = 0; i < n; i++) {
		v[i] = {W[i], B[i], A[i]};
	}
	sort(qr.begin(), qr.end());
	sort(v.begin(), v.end());
	init();
	vector<pair<int, int>> a;
	for (int i = 1; i < n; i++) {
		a.push_back({v[i][0] - v[i-1][0], i});
		if (i > 1)a.push_back({v[i][0] - v[i-2][0], i});
	}
	sort(a.begin(), a.end());
	int cur = 0;
	for (auto &[d, id] : qr) {
		cd = d;
		while (cur < a.size() && a[cur].first <= cd) {
			upd(0, n-1, 0, a[cur++].second);
		}
		ans[id] = t[0].a[0][0];
	}
	return ans;
}

Compilation message (stderr)

nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:127:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |   while (cur < a.size() && a[cur].first <= cd) {
      |          ~~~~^~~~~~~~~~

• 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