Submission #1233565

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233565		AMnu	Nile (IOI24_nile)	C++20	100 / 100	73 ms	9800 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int MAXN = 1e5+5, INF = 1e9+5;

int N, Q, C[MAXN], P[MAXN], Z[MAXN], even[MAXN], odd[MAXN], can[MAXN];
ll ans;
pii SW[MAXN], SE[MAXN], S[2*MAXN];

int find(int x) {
	if (P[x] == x) {
		return x;
	}
	return P[x] = find(P[x]);
}

int score(int p) {
	if (Z[p]&1) {
		return min(can[p],odd[p]);
	}
	return 0;
}

void join(int x,int y) {
	x = find(x);
	y = find(y);
	ans -= score(x);
	ans -= score(y);
	can[x] = min(can[x],can[y]);
	if (Z[x]&1) {
		odd[x] = min(odd[x],even[y]);
		even[x] = min(even[x],odd[y]);
	}
	else {
		odd[x] = min(odd[x],odd[y]);
		even[x] = min(even[x],even[y]);
	}
	P[y] = x;
	Z[x] += Z[y];
	ans += score(x);
}

void add(int x) {
	int px = find(x);
	ans -= score(px);
	can[px] = min(can[px],C[x]);
	ans += score(px);
}

vector<ll> calculate_costs(vector<int> W,vector<int> A,vector<int> B,vector<int> E) {
	N = W.size();
	Q = E.size();
	vector <ll> res(Q);
	for (int i=0;i<N;i++) {
		SW[i] = {W[i],i};
		ans += A[i];
	}
	sort(SW,SW+N);
	for (int i=0;i<N;i++) {
		P[i] = i;
		Z[i] = 1;
		odd[i] = C[i] = A[SW[i].se]-B[SW[i].se];
		even[i] = can[i] = INF;
	}
	for (int i=1;i<N;i++) {
		S[i] = {SW[i].fi-SW[i-1].fi,i};
	}
	for (int i=1;i<N-1;i++) {
		S[i+N-1] = {SW[i+1].fi-SW[i-1].fi,-i};
	}
	sort(S+1,S+2*N-2);
	S[2*N-2].fi = INF;
	for (int i=0;i<Q;i++) {
		SE[i] = {E[i],i};
	}
	sort(SE,SE+Q);
	for (int i=0,j=1;i<Q;i++) {
		while (S[j].fi <= SE[i].fi) {
			if (S[j].se > 0) {
				join(S[j].se-1,S[j].se);
			}
			else {
				add(-S[j].se);
			}
			j++;
		}
		res[SE[i].se] = ans;
	}
	return res;
}

• 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