Submission #1269726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269726		Ekber_Ekber	Horses (IOI15_horses)	C++20	0 / 100	73 ms	60228 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define int long long
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;

constexpr int MAX = 2e+5 + 1, INF = 2e+16, MOD = 1e+9 + 7, K = 31;

int n;
vector <int> x, y;
vector <pair<pair<double, double>, int>> t;

auto merge(pair<pair<double, double>, int> a, pair<pair<double, double>, int> b) {
	pair<pair<double, double>, int> c;
    if (a.ff.ff > b.ff.ff + a.ff.ss) {
		c = a;
	}
	else {
		c = b;
		c.ff.ff += a.ff.ss;
		c.ss = (c.ss * a.ss) % MOD;
	}
	c.ff.ss = a.ff.ss + b.ff.ss;
	return c;
}

void build(int v, int tl, int tr) {
	if (tl == tr) {
		double lx = log10(x[tl]);
		double ly = log10(y[tl]);
		t[v].ff.ff = lx + ly;
		t[v].ff.ss = lx;
		t[v].ss = (x[tl] * y[tl]) % MOD;
		return;
	}
	int tm = (tl + tr) / 2;
	build(v*2, tl, tm);
	build(v*2+1, tm+1, tr);
	t[v] = merge(t[v*2], t[v*2+1]);
}

void update(int v, int tl, int tr, int i, int a, int b) {
	if (tl == tr) {
		double lx = log10(a);
		double ly = log10(b);
		t[v].ff.ff = lx + ly;
		t[v].ff.ss = lx;
		t[v].ss = (a * b) % MOD;
		return;
	}
	int tm = (tl + tr) / 2;
	if (i <= tm) update(v*2, tl, tm, i, a, b);
	else update(v*2+1, tm+1, tr, i, a, b);
	t[v] = merge(t[v*2], t[v*2+1]);
}

void updx(int i, int a) {
	update(1, 0, n-1, i, a, y[i]);
}

void updy(int i, int b) {
	update(1, 0, n-1, i, x[i], b);
}

int32_t init(int32_t n1, int32_t a[], int32_t b[]) {
	n = n1;
	for (int i=0; i < n1; i++) x.pb(a[i]), y.pb(b[i]);
	t.resize(4*(n+2));
	build(1, 0, n-1);
	return (int32_t)t[1].ss;
}

int32_t updateX(int32_t pos, int32_t val) {	
	updx(pos, val);
	return (int32_t)t[1].ss;
}

int32_t updateY(int32_t pos, int32_t val) {
	updy(pos, val);
	return (int32_t)t[1].ss;
}

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