제출 #1244656

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1244656		allin27x	나일강 (IOI24_nile)	C++20	100 / 100	177 ms	26932 KiB

nile

#include <bits/stdc++.h>
using namespace std;
#define int long long

struct _obj {
	int a, b, w;
};

struct rg {
	int l , r, sum, mn0, mn1, ans;
};

struct _lnk {
	int df;
	int idx; //with idx+1
};

bool comp1(_obj a, _obj b) {
	return a.w < b.w;
}
bool comp2(_lnk a, _lnk b) {
	return a.df < b.df;
}

int res = 0;
const int N = 1e5+5;
const int INF = 1e18;
rg Z[N];

set<int> lfs,rgs;
void join(int i) {
	rg R; R.l = Z[i].l; R.r = Z[i+1].r;
	R.sum = Z[i].sum + Z[i+1].sum; res -= Z[i].ans; res -= Z[i+1].ans;
	if ((Z[i].r - Z[i].l + 1)&1) swap(Z[i+1].mn0, Z[i+1].mn1);
	R.mn0 = min(Z[i].mn0, Z[i+1].mn0); R.mn1 = min(Z[i].mn1, Z[i+1].mn1);
	if ((R.r - R.l)&1) R.ans = R.sum; else R.ans = R.sum + R.mn0;
	res += R.ans;
	rgs.erase(i); lfs.erase(i+1);
	Z[R.l] = R; Z[R.r] = R;
}

void upd(int i, int nv) {
	int r = *rgs.lower_bound(i);
	rg R = Z[r]; res -= R.ans;
	R.mn0 = min(R.mn0, nv); R.mn1 = min(R.mn1, nv);
	if ((R.r - R.l)&1) R.ans = R.sum; else R.ans = R.sum + R.mn0;
	res += R.ans;
	Z[R.l] = R; Z[R.r] = R;
}

vector<long long> calculate_costs(vector<signed> W, vector<signed> A, vector<signed> B, vector<signed> E) {
	int n = W.size();
	vector<_obj> p(n); for (int i=0; i<n; i++) p[i].a = A[i], p[i].b = B[i], p[i].w = W[i];
	sort(p.begin(), p.end(), comp1);
	vector<_lnk> evs;
	for (int i=0; i<n-1; i++) {
		_lnk t; t.df = p[i+1].w - p[i].w; t. idx = i;
		evs.push_back(t);
	}
	sort(evs.begin(), evs.end(), comp2);
	vector<pair<int,int>> qs;
	vector<int> ans((int)E.size());
	for (int i=0; i<E.size(); i++) qs.push_back({E[i], i});
	sort(qs.begin(), qs.end());
	for (int i=0; i<n; i++) {
		lfs.insert(i); rgs.insert(i);
		Z[i].l = i; Z[i].r = i; Z[i].sum = p[i].b;
		Z[i].mn0 = p[i].a-p[i].b; Z[i].ans = p[i].a; Z[i].mn1 = INF;
		res += p[i].a;
	}
	vector<_lnk> ps2;
	for (int i=1; i<n-1; i++) {
		_lnk t; t.df = p[i+1].w - p[i-1].w; t.idx = i;
		ps2.push_back(t);
	}
	sort(ps2.begin(), ps2.end(), comp2);
	int j=0; int t = 0;
	for (auto [d, idx]: qs) {
		while (j<evs.size() && evs[j].df <= d) {
			join(evs[j].idx); j++;
		}
		while (t<ps2.size() && ps2[t].df <= d) {
			int i = ps2[t].idx;
			upd(i, p[i].a - p[i].b);
			t++;
		}
		ans[idx] = res;

	}
	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