Submission #1102054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102054		Berryisbetter	Nile (IOI24_nile)	C++17	100 / 100	170 ms	30548 KiB

nile

#include <bits/stdc++.h>
#include "nile.h"
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vvll = vector<vll>;
const ll INF = 1e9;
vll EMPTY = {};
vll a, b, w;
struct Sum {
	ll n;
	vll sum;
	//Sum();
	Sum(vll& a) :n(a.size()), sum(n + 1) {
		for (ll i = 0; i < n; i++) {
			sum[i + 1] = sum[i] + a[i];
		}
	}
	ll qu(ll l, ll r) {
		return sum[r] - sum[l];
	}
};
struct Seg {
	ll n;
	vll a;
	//Seg();
	Seg(vll& v) :n(v.size()), a(2 * n) {
		for (ll i = 0; i < n; i++) {
			a[i + n] = v[i];
		}
		for (ll i = n - 1; i > 0; i--) {
			a[i] = max(a[i * 2], a[i * 2 + 1]);
		}
	}
	void up(ll i, ll x) {
		i += n;
		a[i] = x;
		while (i > 1) {
			i /= 2;
			a[i] = max(a[i * 2], a[i * 2 + 1]);
		}
	}
	ll qu(ll l, ll r) {
		ll ans = -INF;
		for (l += n, r += n; l < r; l /= 2, r /= 2) {
			if (l % 2) {
				ans = max(ans,a[l++]);
			}
			if (r % 2) {
				ans = max(ans,a[--r]);
			}
		}
		return ans;
	}
};
Sum sumall(EMPTY);
Seg segall(EMPTY), segeven(EMPTY), segodd(EMPTY);
ll calc(ll l, ll r) {
	ll sub = 0;
	if ((r - l) % 2 == 1) {
		if (l % 2 == 0) {
			sub = max(segall.qu(l, r), segeven.qu(l, r));
		}
		else {
			sub = max(segall.qu(l, r), segodd.qu(l, r));
		}
	}
	return sumall.qu(l, r) - sub;
}


std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E) {
	ll n = A.size(), q = E.size();
	vector<pair<ll, pll>> ord(n);
	for (ll i = 0; i < n; i++) {
		ord[i] = { W[i],{A[i],B[i]} };
	}
	sort(ord.begin(), ord.end());
	//a = A, b = B, w = W; in correct order:
	a = b = w = vll(n);
	for (ll i = 0; i < n; i++) {
		w[i] = ord[i].first;
		a[i] = ord[i].second.first;
		b[i] = ord[i].second.second;
	}

	//setup rmq rsq:
	sumall = Sum(b);
	vll temp, rem=b;
	for (ll i = 0; i < n; i++) {
		rem[i] -= a[i];
	}
	temp=rem;
	segall = Seg(temp);
	for (ll i = 0; i < n; i += 2) {
		temp[i] = -INF;
	}
	segodd = Seg(temp);
	temp = rem;
	for (ll i = 1; i < n; i += 2) {
		temp[i] = -INF;
	}
	segeven = Seg(temp);
	temp = rem;

	//setup ev:
	vector<pair<ll, pll>> ev;// {len,{type,inx}}. type: 0 - query,1 - next disconnect,2 - disconnect two steps
	for (ll i = 0; i < q; i++) {
		ev.push_back({ E[i]+1,{0,i} });//?
	}
	for (ll i = 0; i < n - 1; i++) {
		ev.push_back({ w[i + 1] - w[i],{1,i} });//+1?
	}
	for (ll i = 0; i < n - 2; i++) {
		ev.push_back({ w[i + 2] - w[i],{2,i} });//+1?
	}
	sort(ev.begin(), ev.end());
	reverse(ev.begin(), ev.end());

	// solve:
	vll ans(q);
	ll sum = calc(0, n);
	set<pll> segs = { { 0ll,n } };
	for (auto k : ev) {
		ll type = k.second.first, inx = k.second.second;
		if (type == 0) {
			ans[inx] = sum;
		}
		if (type == 1) {
			auto p = segs.upper_bound({ inx,INF });
			p--;
			ll l = (*p).first, r = (*p).second;
			sum -= calc(l, r);
			segs.erase(p);
			sum += calc(l, inx + 1);
			sum += calc(inx + 1, r);
			segs.insert({ l, inx + 1 });
			segs.insert({inx + 1, r});
		}
		if (type == 2) {
			auto p = segs.upper_bound({ inx,INF });
			p--;
			ll l = (*p).first, r = (*p).second;
			sum -= calc(l, r);
			segall.up(inx+1, -INF);//?+1
			sum += calc(l, r);
		}
	}
	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