Submission #1226916

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226916		alterio	Nile (IOI24_nile)	C++20	45 / 100	82 ms	24628 KiB

nile

#include <bits/stdc++.h>
#include "nile.h"

using namespace std;

#define ll long long
#define all(x) (x).begin(), (x).end()

const int mxn = 1e5 + 100;

struct S {
	ll W, A, B;
};

bool operator < (S a, S b) {
	if (a.W != b.W) return a.W < b.W;
	if (a.A != b.A) return a.A < b.A;
	return a.B < b.B;
}

struct O {
	ll diff, indI, indJ;
};

bool operator < (O a, O b) {
	if (a.diff != b.diff) return a.diff < b.diff;
	if (a.indI != b.indI) return a.indI < b.indI;
	return a.indJ < b.indJ;
}

ll res = 0;

ll ldr[mxn], rnk[mxn], ans[mxn], L[mxn], R[mxn], sumA[mxn], sumB[mxn], mnOddS[mxn], mnEvenS[mxn], mnOddJ[mxn], mnEvenJ[mxn];

void umin(ll &x, ll y) {
	x = min(x, y);
}

void umax(ll &x, ll y) {
	x = max(x, y);
}

int Find(int x) {
	if (ldr[x] == x) return x;
	return ldr[x] = Find(ldr[x]);
}

bool Same(int x, int y) {
	return Find(x) == Find(y);
}

void Union(int x, int y) {
	x = Find(x), y = Find(y);
	if (x == y) return;
	if (rnk[y] > rnk[x]) swap(x, y);
	ldr[y] = x;
	rnk[x] += rnk[y];
	sumA[x] += sumA[y];
	sumB[x] += sumB[y];
	umin(L[x], L[y]);
	umax(R[x], R[y]);
	umin(mnOddS[x], mnOddS[y]);
	umin(mnEvenS[x], mnEvenS[y]);
	umin(mnOddJ[x], mnOddJ[y]);
	umin(mnEvenJ[x], mnEvenJ[y]);
}

ll prfA[mxn], prfB[mxn];

ll getB(int l, int r) {
	return prfB[r] - (l == 0 ? 0 : prfB[l - 1]);
}

ll getA(int l, int r) {
	return prfA[r] - (l == 0 ? 0 : prfA[l - 1]);
}

vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
	int N = W.size(), Q = (int) E.size();
    vector<ll> Res(Q, 0);
    vector<pair<ll, ll>> Qr;
	for (int i = 0; i < Q; i++) Qr.push_back({E[i], i});
	sort(all(Qr));
	vector<S> V;
	for (int i = 0; i < N; i++) V.push_back({W[i], A[i], B[i]}), res += A[i];
	sort(all(V));
	for (int i = 0; i < N; i++) {
		ldr[i] = i, L[i] = i, R[i] = i;
		ans[i] = V[i].A;
		rnk[i] = 1, sumA[i] = V[i].A, sumB[i] = V[i].B;
		mnOddS[i] = mnEvenS[i] = mnOddJ[i] = mnEvenJ[i] = 1e15;
		if (i) prfA[i] = prfA[i - 1], prfB[i] = prfB[i - 1];
		prfA[i] += V[i].A,
		prfB[i] += V[i].B;
	}
	vector<O> Ord;
	for (int i = 0; i < N; i++) {
		if (i + 1 < N) Ord.push_back({V[i + 1].W - V[i].W, i, i + 1});
		if (i + 2 < N) Ord.push_back({V[i + 2].W - V[i].W, i, i + 2});
	}
	sort(all(Ord));
	int last = 0;
	for (auto x : Qr) {
		while (last < Ord.size() && Ord[last].diff <= x.first) {
			int indI = Ord[last].indI, indJ = Ord[last].indJ;
			// cout << indI << " " << indJ << " : " << Ord[last].diff << endl;
			if (Same(indI, indJ) && indI + 1 == indJ) {
				last++;
				continue;
			}
			if (!Same(indI, indJ)) {
				res -= ans[Find(indI)];
				res -= ans[Find(indJ)];
				Union(indI, indJ);
			}
			else res -= ans[Find(indI)];
			int X = Find(indI), posL = L[X], posR = R[X];
			// cout << X << " - " << L[X] << " " << R[X] << endl;
			if (indI + 1 == indJ) {
				bool even = (indI % 2 == 0);
				if (even) umin(mnEvenS[X], V[indI].A - V[indI].B);
				else umin(mnOddS[X], V[indI].A - V[indI].B);
				even = (indJ % 2 == 0);
				// if (indJ == 4) {
				// 	cout << "SURPRISE MOTHERFUCKER : " << even << " " << V[indJ].A - V[indJ].B << endl;
				// }
				if (even) umin(mnEvenS[X], V[indJ].A - V[indJ].B);
				else umin(mnOddS[X], V[indJ].A - V[indJ].B);
			}
			else {
				int ind = indI + 1;
				bool even = (ind % 2 == 0);
				if (even) umin(mnEvenJ[X], V[ind].A - V[ind].B);
				else umin(mnOddJ[X], V[ind].A - V[ind].B);
			}
			if (rnk[X] % 2 == 0) ans[X] = sumB[X];
			else {
				ll least = 1e15;
				if (posL % 2 == 0) umin(least, mnEvenS[X]), umin(least, mnOddJ[X]);
				else umin(least, mnOddS[X]), umin(least, mnEvenJ[X]);
				// cout << "! " << sumB[X] << " " << least << endl;
				ans[X] = sumB[X] + least;
			}
			res += ans[X];
			// cout << res << endl;
			last++;
		}
		// cout << endl;
		Res[x.second] = res;
	}
	return Res;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 15 / 15
• Subtask 7: 0 / 18