Submission #834269

#	Time	Username	Problem	Language	Result	Execution time	Memory
834269		Tigerpants	Horses (IOI15_horses)	C++17	100 / 100	531 ms	231352 KiB

horses

#include "horses.h"
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cmath>
#include "math.h"

using namespace std;

typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef long double ld;
typedef vector<ld> vld;
typedef vector<vld> vvld;
typedef pair<ll, ll> pll;
typedef pair<ll, ld> pll_ld;
typedef pair<ld, ll> pld_ll;
typedef vector<pll> vpll;
typedef vector<pll_ld> vpll_ld;
typedef vector<pld_ll> vpld_ll;
typedef pair<pld_ll, ll> ppld_ll_ll;
typedef vector<ppld_ll_ll> vppld_ll_ll;

const ll MOD = 1000000007;
//const ll INFLL = ((MOD + 1) * (MOD + 1)) + 1;
//const ld INFLD = 1000000000000000001.0;

#define rep(i, a, b) for (ll i = a; i < b; i++)
#define sz(a) (ll) a.size()
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)

const pld_ll NONE_pld_ll = mp(1.0, 0);
const pld_ll NONE_pld_ll_lazy = mp(0.0, 1);
const ppld_ll_ll NONE_ppld_ll_ll = mp(NONE_pld_ll, 1);

ld LOG(ld v) {return log2l(v);}

ll n;

ppld_ll_ll comb(ppld_ll_ll lhs, ppld_ll_ll rhs) {
	return mp(max<pld_ll>(rhs.first, lhs.first), (rhs.second * lhs.second) % MOD);
}
vppld_ll_ll segtree; // ((max price, index), horses)
vpll interval;
vpld_ll lazy; // (price change, horses change)

void build(ll cur, ll left, ll right, vpld_ll& init_values) {
	interval[cur] = mp(left, right);
	lazy[cur] = NONE_pld_ll_lazy;

	if (left == right) {
		segtree[cur] = mp(mp(init_values[left].first, left), init_values[left].second);
		return;
	}

	ll mid = (left + right) / 2;
	build(2 * cur, left, mid, init_values);
	build(2 * cur + 1, mid + 1, right, init_values);
	segtree[cur] = comb(segtree[2 * cur], segtree[2 * cur + 1]);
}

ppld_ll_ll operator+(const ppld_ll_ll& lhs, const pld_ll& rhs) {
	return mp(mp(lhs.first.first + rhs.first, lhs.first.second), (lhs.second * rhs.second) % MOD);
}
pld_ll operator+(const pld_ll& lhs, const pld_ll& rhs) {
	return mp(lhs.first + rhs.first, (lhs.second * rhs.second) % MOD);
}

void propagate(ll cur) {
	segtree[cur] = segtree[cur] + lazy[cur];
	if (interval[cur].first != interval[cur].second) {
		lazy[2 * cur] = lazy[2 * cur] + lazy[cur];
		lazy[2 * cur + 1] = lazy[2 * cur + 1] + lazy[cur];
	}
	lazy[cur] = NONE_pld_ll_lazy;
}

void update(ll cur, ll left, ll right, pld_ll delta) {
	propagate(cur);
	if ((interval[cur].first > right) || (interval[cur].second < left)) return;

	if ((interval[cur].first >= left) && (interval[cur].second <= right)) {
		lazy[cur] = lazy[cur] + delta;
		propagate(cur);
		return;
	}

	update(2 * cur, left, right, delta);
	update(2 * cur + 1, left, right, delta);
	segtree[cur] = comb(segtree[2 * cur], segtree[2 * cur + 1]);
}

ppld_ll_ll query(ll cur, ll left, ll right) {
	propagate(cur);
	if ((interval[cur].first > right) || (interval[cur].second < left)) {
		return NONE_ppld_ll_ll;
	}

	if ((interval[cur].first >= left) && (interval[cur].second <= right)) {
		return segtree[cur];
	}

	return comb(query(2 * cur, left, right), query(2 * cur + 1, left, right));
}

vld x;
vld y;
vll XLL;
vll YLL;

ll max_money() {
	ppld_ll_ll q = query(1, 0, n - 1);
	ll index = q.first.second;
	ppld_ll_ll r = query(1, index, index);
	//cout << "((" << q.first.first << ", " << q.first.second << "), " << q.second << ") -> ((" << r.first.first << ", " << r.first.second << "), " << r.second << ")" << endl;
	return (r.second * YLL[index]) % MOD;
}


int init(int N, int X[], int Y[]) {
	n = N;

	x.resize(n);
	y.resize(n);
	XLL.resize(n);
	YLL.resize(n);
	rep(i, 0, n) {
		x[i] = LOG((ld) X[i]);
		y[i] = LOG((ld) Y[i]);
		XLL[i] = (ll) X[i];
		YLL[i] = (ll) Y[i];
	}

	vpld_ll init_values(n);
	ld h = 0.0;
	ll H = 1;
	rep(i, 0, n) {
		h += x[i];
		H *= XLL[i]; H %= MOD;
		init_values[i] = mp(h + y[i], H);
	}

	segtree.resize(4 * n);
	interval.resize(4 * n);
	lazy.resize(4 * n);
	build(1, 0, n - 1, init_values);

	return (int) max_money();
}

ll binary_exponentiation(ll b, ll e) {
	if (e == 0) return 1;
	ll d = binary_exponentiation(b, e >> 1);
	d = (d * d) % MOD;
	return (e & 1) ? (d * b) % MOD : d;
}

int updateX(int pos, int val) {
	ld new_h = LOG((ld) val);
	ld delta = new_h - x[pos];
	x[pos] = new_h;
	
	ll DELTA = (((ll) val) * binary_exponentiation(XLL[pos], MOD - 2)) % MOD;
	XLL[pos] = (ll) val;

	update(1, pos, n - 1, mp(delta, DELTA));

	return (int) max_money();
}

int updateY(int pos, int val) {
	ld new_p = LOG((ld) val);
	ld delta = new_p - y[pos];
	y[pos] = new_p;

	update(1, pos, pos, mp(delta, 1));

	YLL[pos] = (ll) val;

	return (int) max_money();
}

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 23 / 23