Submission #1104604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104604		Nonoze	Nile (IOI24_nile)	C++17	100 / 100	103 ms	21964 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define cmax(a, b) a=max(a, b)
#define cmin(a, b) a=min(a, b)
#define fi first
#define se second

vector<pair<int, int>> leftt;

int calc(int d, int l, int r) { int n=r-l+1;
	if ((r-l+1)%2==0) return 0;
	int ans=min(leftt[l].se, leftt[r].se);
	for (int i=l; i<=r; i+=2) cmin(ans, leftt[i].se);
	for (int i=l; i<n-1; i++) {
		if (leftt[i+1].fi-leftt[i-1].fi<=d) cmin(ans, leftt[i].se);
	}
	return ans;
}

int n, q, base;
vector<pair<int, int>> a;
vector<int> par, szz, odd, even, best;

int getpar(int x) {
	if (x==par[x]) return x;
	return par[x]=getpar(par[x]);
}

void merge(int a, int &ans) {
	int b=a+1;
	a=getpar(a), b=getpar(b);
	if (a==b) return;
	ans-=(szz[a]%2)*min(best[a], odd[a])+(szz[b]%2)*min(best[b], odd[b]);
	if (szz[a]%2) swap(odd[b], even[b]);
	cmin(odd[a], odd[b]), cmin(even[a], even[b]), cmin(best[a], best[b]);
	szz[a]+=szz[b];
	par[b]=a;
	ans+=(szz[a]%2)*min(best[a], odd[a]);
}

void add(int a, int val, int &ans) {
	a=getpar(a);
	ans-=(szz[a]%2)*min(best[a], odd[a]);
	cmin(best[a], val);
	ans+=(szz[a]%2)*min(best[a], odd[a]);
}

vector<int> calculate_costs(vector<signed> _w, vector<signed> _a, vector<signed> _b, vector<signed> e) { n=sz(_w), q=sz(e);
	base=0;
	int ans=0;
	for (int i=0; i<n; i++) base+=(int)_b[i], _a[i]-=_b[i];
	for (int i=0; i<n; i++) a.pb({_w[i], _a[i]}), ans+=_a[i];
	sort(all(a));
	par.resize(n, 0), szz.resize(n, 1); iota(all(par), 0);
	odd.resize(n), even.resize(n, 1e18), best.resize(n, 1e18);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq2;
	for (int i=0; i<n-1; i++) pq.push({a[i+1].fi-a[i].fi, i});
	for (int i=1; i<n-1; i++) pq2.push({a[i+1].fi-a[i-1].fi, i});
	for (int i=0; i<n; i++) odd[i]=a[i].se;
	vector<int> answers(q);
	vector<pair<int, int>> queries;
	for (int i=0; i<q; i++) queries.pb({e[i], i});
	sort(all(queries));
	for (auto [d, pos]: queries) {
		while (!pq.empty() && pq.top().fi<=d) {
			merge(pq.top().se, ans);
			pq.pop();
		}
		while (!pq2.empty() && pq2.top().fi<=d) {
			add(pq2.top().se, a[pq2.top().se].se, ans);
			pq2.pop();
		}
		answers[pos]=base+ans;
	}
	return answers;
}

• 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