Submission #1189045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189045		raspy	Horses (IOI15_horses)	C++20	0 / 100	1597 ms	52808 KiB

horses

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

#define ll long long

using namespace std;

const int MAX_N = 5e5+5;
const int mod = 1e9+7;

ll n;
set<ll> st;
pair<ll, ll> seg[MAX_N*4];
ll x[MAX_N+5];
ll y[MAX_N+5];

void upd(ll v, ll l, ll r, ll ix, pair<ll, ll> tr)
{
	if (l == r)
	{
		seg[v] = tr;
		return;
	}
	ll mid = (l + r) / 2;
	if (ix <= mid)
		upd(v*2+1, l, mid, ix, tr);
	else if (ix > mid)
		upd(v*2+2, mid+1, r, ix, tr);
	seg[v].second = max(seg[v*2+2].second, seg[v*2+1].second);
	seg[v].first = seg[v*2+1].first*seg[v*2+2].first%mod;
}

pair<ll, ll> qr(ll v, ll l, ll r, ll i, ll j)
{
	if (l > r || i > j)
		return {1, 0};
	if (i <= l && j >= r)
		return seg[v];
	ll mid = (l + r) / 2;
	pair<ll, ll> lv = qr(v*2+1, l, mid, i, min(j, mid));
	pair<ll, ll> ds = qr(v*2+2, mid+1, r, max(i, mid+1), j);
	return {lv.first*ds.first%mod, max(lv.second, ds.second)};
}

ll getMax()
{
	pair<ll, ll> t = qr(0, 0, n-1, 0, n-1);
	ll rez = t.first*y[n-1]%mod;
	ll j = n-1, pry = y[n-1];
	vector<ll> zac;
	for (ll i = 0; i < 30 && st.size(); i++)
	{
		zac.push_back(*st.rbegin());
		ll tj = *st.rbegin();
		st.erase(tj);
		t = qr(0, 0, n-1, tj+1, j);
		if (t.first >= mod)
			break;
		if (t.first*pry < t.second)
		{
			j = tj;
			pry = t.second;
			t = qr(0, 0, n-1, 0, j);
			rez = t.first*pry%mod;
		}
	}
	for (ll v : zac)
		st.insert(v);
	return rez%mod;
}

int init(int N, int X[], int Y[])
{
	n = N;
	for (ll i = 0; i < n; i++)
	{
		x[i] = X[i]; y[i] = Y[i];
		if (X[i] != 1)
			st.insert(i);
		upd(0, 0, n-1, i, {X[i], Y[i]});
	}
	return getMax();
}

int updateX(int pos, int val)
{
	if (val != 1)
		st.insert(pos);
	else if (st.count(pos))
		st.erase(pos);
	x[pos] = val;
	upd(0, 0, n-1, pos, {x[pos], y[pos]});
	return getMax();
}

int updateY(int pos, int val)
{
	y[pos] = val;
	upd(0, 0, n-1, pos, {x[pos], y[pos]});
	return getMax();
}

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