Submission #1246654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246654		inkvizytor	Horses (IOI15_horses)	C++20	100 / 100	121 ms	46404 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long

ll M = 1e9+7;

vector<ll> tr (1<<20, 0), y (1<<20);
vector<double> sm (1<<20, 0);
vector<pair<double, int>> mx (1<<20, {0, 0});

ll mult(int v, int p, int k, int a, int b) {
	if (a <= p && k <= b) {
		return tr[v];
	}
	if (b < p || k < a) {
		return 1;
	}
	return (mult(v*2, p, (p+k)/2, a, b)*mult(v*2+1, (p+k)/2+1, k, a, b))%M;
}

int maks() {
	int a = mx[1].second;
	return (int)((mult(1, 0, (1<<19)-1, 0, a)*y[a])%M);
}

int init(int n, int X[], int Y[]) {
	for (int i = 0; i < n; i++) {
		tr[i+(1<<19)] = X[i];
		y[i] = Y[i];
		sm[i+(1<<19)] = log2(X[i]);
		mx[i+(1<<19)] = {log2(X[i])+log2(Y[i]), i};
	}
	for (int i = (1<<19)-1; i > 0; i--) {
		tr[i] = (tr[i*2]*tr[i*2+1])%M;
		sm[i] = sm[i*2]+sm[i*2+1];
		mx[i] = max(mx[i*2], {sm[i*2]+mx[i*2+1].first, mx[i*2+1].second});
	}
	return maks();
}

void upd(int i) {
	i += 1<<19;
	while(i>1) {
		i/=2;
		tr[i] = (tr[i*2]*tr[i*2+1])%M;
		sm[i] = sm[i*2]+sm[i*2+1];
		mx[i] = max(mx[i*2], {sm[i*2]+mx[i*2+1].first, mx[i*2+1].second});
	}
}

int updateX(int pos, int val) {	
	tr[pos+(1<<19)] = val;
	sm[pos+(1<<19)] = log2(val);
	mx[pos+(1<<19)].first = log2(val)+log2(y[pos]);
	upd(pos);
	return maks();
}

int updateY(int pos, int val) {
	y[pos] = val;
	mx[pos+(1<<19)].first = sm[pos+(1<<19)]+log2(val);
	upd(pos);
	return maks();
}

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