Submission #1123648

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123648		Tob	Nile (IOI24_nile)	C++20	100 / 100	158 ms	21548 KiB

nile

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

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 1e5 + 7, ofs = (1 << 17), inf = 1e9;

ll cur;
int par[N], siz[N], sol[N][2];
int t[2*ofs];

void add(int x, int y) {
	x += ofs;
	t[x] = y;
	while (x /= 2) t[x] = min(t[2*x], t[2*x+1]);
}
int query(int x, int a, int b, int lo = 0, int hi = ofs-1) {
	if (b < lo || hi < a) return inf;
	if (a <= lo && hi <= b) return t[x];
	int mid = (lo + hi) / 2;
	return min(query(2*x, a, b, lo, mid), query(2*x+1, a, b, mid+1, hi));
}

inline ll cost(int x) {return (siz[x] % 2 == 0) ? 0 : min(query(1, x, x+siz[x]-1), sol[x][x%2]);}

int find(int x) {return (x == par[x]) ? x : (par[x] = find(par[x]));}
void unite(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y) return;
	if (x > y) swap(x, y);
	cur -= cost(x)+cost(y);
	par[y] = x;
	siz[x] += siz[y];
	for (int i = 0; i < 2; i++) sol[x][i] = min(sol[x][i], sol[y][i]);
	cur += cost(x);
}

vector <ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
	int n = W.size(), q = E.size();
	fill(t, t+2*ofs, inf);
	ll res = 0;
	for (int i = 0; i < n; i++) res += B[i], A[i] -= B[i], cur += A[i];
	vector <pii> tmp;
	for (int i = 0; i < n; i++) tmp.pb({W[i], A[i]});
	sort(all(tmp));
	for (int i = 0; i < n; i++) W[i] = tmp[i].F, A[i] = tmp[i].S;
	
	for (int i = 0; i < n; i++) par[i] = i, siz[i] = 1, sol[i][i%2] = A[i], sol[i][i%2==0] = inf;
	
	vector <pair <pii, int> > v;
	for (int j = 0; j < 2; j++) for (int i = 0; i < n-j-1; i++) v.pb({{W[i+j+1]-W[i], j}, i});
	for (int i = 0; i < q; i++) v.pb({{E[i], 2}, i});
	sort(all(v));
	vector <ll> ans(q);
	
	for (auto it : v) {
		int x = it.S;
		if (!it.F.S) unite(x, x+1);
		else if (it.F.S == 1) {
			cur -= cost(find(x));
			add(x+1, A[x+1]);
			cur += cost(find(x));
		}
		else ans[x] = res+cur;
	}
	
	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