Submission #1269741

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269741		Ekber_Ekber	말 (IOI15_horses)	C++20	100 / 100	227 ms	201128 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define int long long
#define double long double
#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>, pair<int, int>>> t;

auto merge(pair<pair<double, double>, pair<int, int>> a, pair<pair<double, double>, pair<int, int>> b) {
	pair<pair<double, double>, pair<int, 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.ff = (c.ss.ff * a.ss.ss) % MOD;
	}
	c.ff.ss = a.ff.ss + b.ff.ss;
	c.ss.ss = (a.ss.ss * b.ss.ss) % MOD;
	return c;
}

void build(int v, int tl, int tr) {
	if (tl == tr) {
		double lx = log10(1. * x[tl]);
		double ly = log10(1. * y[tl]);
		t[v].ff.ff = lx + ly;
		t[v].ff.ss = lx;
		t[v].ss.ff = (x[tl] * y[tl]) % MOD;
		t[v].ss.ss = x[tl];
		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.ff = (a * b) % MOD;
		t[v].ss.ss = a;
		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]);
	x[i] = a;
}

void updy(int i, int b) {
	update(1, 0, n-1, i, x[i], b);
	y[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(8*(n+2));
	build(1, 0, n-1);
	return (int32_t)t[1].ss.ff;
}

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

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

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