Submission #369762

#	Time	Username	Problem	Language	Result	Execution time	Memory
369762		LucaDantas	Horses (IOI15_horses)	C++17	17 / 100	55 ms	28140 KiB

horses

#include "horses.h"
#include<cmath>
#include<algorithm>
#include <cassert>
#include <cstdio>
using namespace std;

#define double long double

using pdi = pair<double, int>;

#define ff first
#define ss second

constexpr int maxn = 5e5+10, mod = 1000000007;
constexpr double eps = 1e-4;

int *x, *y, n, val_pref[maxn];

double pref[maxn];

int power(int b, int e) {
	int ans = 1;
	while(e) {
		if(e&1) ans = (int)(1ll * ans * b % mod);
		b = (int)(1ll * b * b % mod);
		e >>= 1;
	}
	return ans;
}

// struct SegmentTree
// {
// 	pdi tree[4*maxn], lazy[4*maxn];
// 	void build(int node, int i, int j) {
// 		if(i == j) {
// 			tree[node] = {pref[i] + log2(y[i]), (int)(1ll * val_pref[i] * y[i] % mod)};
// 			return;
// 		}
// 		int m = (i+j) >> 1;
// 		build(2*node, i, m); build(2*node+1, m+1, j);
// 		tree[node] = max(tree[2*node], tree[2*node+1]);
// 	}
// 	void flush(int node, int i, int j) {
// 		if(!lazy[node].ff) return;
// 		if(i != j) {
// 			lazy[2*node].ff += lazy[node].ff;
// 			lazy[2*node+1].ff += lazy[node].ff;
// 			lazy[2*node].ss = (int)(1ll * lazy[node].ss * lazy[2*node].ss % mod);
// 			lazy[2*node+1].ss = (int)(1ll * lazy[node].ss * lazy[2*node+1].ss % mod);
// 		}
// 		tree[node].ff += lazy[node].ff;
// 		tree[node].ss = (int)(1ll * tree[node].ss * lazy[node].ss % mod);
// 		lazy[node] = {0, 1};
// 	}
// 	void upd(int node, int i, int j, int l, const pdi& val) {
// 		flush(node, i, j);
// 		if(j < l) return;
// 		if(i >= l) {
// 			lazy[node] = val;
// 			flush(node, i, j);
// 			return;
// 		}
// 		int m = (i+j) >> 1;
// 		upd(2*node, i, m, l, val);
// 		upd(2*node+1, m+1, j, l, val);
// 		tree[node] = max(tree[2*node], tree[2*node+1]);
// 	}
// 	void upd_pos(int node, int i, int j, int pos, const pdi& val) {
// 		flush(node, i, j);
// 		if(i == j) {
// 			lazy[node] = val;
// 			flush(node, i, j); // preguiça de codar o comb dnv kkk
// 			return;
// 		}
// 		int m = (i+j) >> 1;
// 		if(pos <= m) upd_pos(2*node, i, m, pos, val), flush(2*node+1, m+1, j);
// 		else upd_pos(2*node+1, m+1, j, pos, val), flush(2*node, i, m);
// 		tree[node] = max(tree[2*node], tree[2*node+1]);
// 	}
// 	pdi query() {
// 		flush(1, 0, n-1);
// 		return tree[1];
// 	}
// } seg;

int init(int N, int X[], int Y[]) {
	x = X; y = Y; n = N;
	double ans = -1; int int_ans = 0;
	for(int i = 0; i < n; i++) {
		pref[i] = (i?pref[i-1]:0) + log2(x[i]);
		val_pref[i] = (int)(1ll * (i?val_pref[i-1]:1) * x[i] % mod);
		if(pref[i] + log2(y[i]) > ans) {
			// assert(val_pref[i] * y[i] > int_ans);
			ans = pref[i] + log2(y[i]), int_ans = (int)(1ll * val_pref[i] * y[i] % mod);
		}
		// int_ans = max(int_ans, val_pref[i] * y[i]);
	}
	// printf("%lf %d\n", pow(2, ans), int_ans);
	// assert((int)(pow(2, ans)+eps) == int_ans);
	// seg.build(1, 0, n-1);
	// return seg.query().ss;
	return int_ans;
}

int updateX(int pos, int val) {
	assert(0);
	return 0;
	// int mudar = (int)(1ll * val * power(x[pos], mod-2) % mod);
	// pdi v = {log2(val) - log2(x[pos]), mudar};
	// // seg.upd(1, 0, n-1, pos, v);
	// for(int i = pos; i < n; i++) {
	// 	pref[i] += v.ff;
	// 	val_pref[i] = (int)(1ll * val_pref[i] * v.ss % mod);
	// }
	// double ans = 0; int int_ans = 0;
	// for(int i = 0; i < n; i++)
	// 	if(pref[i] + log2(y[i]) > ans)
	// 		ans = pref[i] + log2(y[i]), int_ans = (int)(1ll * val_pref[i] * y[i] % mod);
	// x[pos] = val;
	// return int_ans;
	// // return seg.query().ss;
}

int updateY(int pos, int val) {
	assert(0);
	return 0;
	// // int mudar = (int)(1ll * val * power(y[pos], mod-2) % mod);
	// // pdi v = {log2(val) - log2(y[pos]), mudar};
	// // seg.upd_pos(1, 0, n-1, pos, v);
	// double ans = 0; int int_ans = 0;
	// y[pos] = val;
	// for(int i = 0; i < n; i++)
	// 	if(pref[i] + log2(y[i]) > ans)
	// 		ans = pref[i] + log2(y[i]), int_ans = (int)(1ll * val_pref[i] * y[i] % mod);
	// // return seg.query().ss;
	// return int_ans;
}

Compilation message (stderr)

horses.cpp: In function 'int updateX(int, int)':
horses.cpp:106:17: warning: unused parameter 'pos' [-Wunused-parameter]
  106 | int updateX(int pos, int val) {
      |             ~~~~^~~
horses.cpp:106:26: warning: unused parameter 'val' [-Wunused-parameter]
  106 | int updateX(int pos, int val) {
      |                      ~~~~^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:125:17: warning: unused parameter 'pos' [-Wunused-parameter]
  125 | int updateY(int pos, int val) {
      |             ~~~~^~~
horses.cpp:125:26: warning: unused parameter 'val' [-Wunused-parameter]
  125 | int updateY(int pos, int val) {
      |                      ~~~~^~~

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