Submission #514861

#	Time	Username	Problem	Language	Result	Execution time	Memory
514861		thiago_bastos	Horses (IOI15_horses)	C++17	100 / 100	200 ms	50400 KiB

horses

#include "horses.h"
#include <utility>
#include <vector>
#include <cmath>
#include <algorithm>

const int mod = 1e9 + 7;

using value = std :: pair<double, int>;
using i64 = long long;

std :: vector<value> maxlg;
std :: vector<double> lg;
std :: vector<int> prod, X, Y;
int N;

value op(value a, double b, int c) {
	a.first += b;
	a.second = (i64)a.second * c % mod;
	return a;
}

void load(int lo, int hi, int no = 1) {
	if(lo == hi) {
		maxlg[no] = std :: make_pair(log(X[lo]) + log(Y[lo]), (i64)X[lo] * Y[lo] % mod);
		lg[no] = log(X[lo]);
		prod[no] = X[lo];
	} else {
		int mid = (lo + hi) / 2;
		load(lo, mid, 2 * no);
		load(mid + 1, hi, 2 * no + 1);
		lg[no] = lg[2 * no] + lg[2 * no + 1];
		maxlg[no] = std :: max(maxlg[2 * no], op(maxlg[2 * no + 1], lg[2 * no], prod[2 * no]));
		prod[no] = (i64)prod[2 * no] * prod[2 * no + 1] % mod;
	}
}

void upd(int k, int x, int y, int lo, int hi, int no = 1) {
	if(lo == hi) {
		X[lo] = x, Y[lo] = y;
		maxlg[no] = std :: make_pair(log(X[lo]) + log(Y[lo]), (i64)X[lo] * Y[lo] % mod);
		lg[no] = log(X[lo]);
		prod[no] = X[lo];	
	} else {
		int mid = (lo + hi) / 2;
		if(k <= mid) upd(k, x, y, lo, mid, 2 * no);
		else upd(k, x, y, mid + 1, hi, 2 * no + 1);
		lg[no] = lg[2 * no] + lg[2 * no + 1];
		maxlg[no] = std :: max(maxlg[2 * no], op(maxlg[2 * no + 1], lg[2 * no], prod[2 * no]));
		prod[no] = (i64)prod[2 * no] * prod[2 * no + 1] % mod;		 
	}
}

int init(int N, int X[], int Y[]) {
	int lg = 31 - __builtin_clz(N);
	maxlg.resize(4 << lg);
	prod.resize(4 << lg);
	:: lg.resize(4 << lg);
	:: X.resize(N);
	:: Y.resize(N);
	:: N = N;
	for(int i = 0; i < N; ++i) :: X[i] = X[i], :: Y[i] = Y[i];
	load(0, N - 1);
	return maxlg[1].second;
}

int updateX(int pos, int val) {
	upd(pos, val, Y[pos], 0, N - 1);
	return maxlg[1].second;
}

int updateY(int pos, int val) {
	upd(pos, X[pos], val, 0, N - 1);
	return maxlg[1].second;
}

Compilation message (stderr)

horses.cpp: In function 'value op(value, double, int)':
horses.cpp:19:31: warning: conversion from 'i64' {aka 'long long int'} to 'int' may change value [-Wconversion]
   19 |  a.second = (i64)a.second * c % mod;
      |             ~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void load(int, int, int)':
horses.cpp:34:51: warning: conversion from 'i64' {aka 'long long int'} to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
   34 |   prod[no] = (i64)prod[2 * no] * prod[2 * no + 1] % mod;
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void upd(int, int, int, int, int, int)':
horses.cpp:50:51: warning: conversion from 'i64' {aka 'long long int'} to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
   50 |   prod[no] = (i64)prod[2 * no] * prod[2 * no + 1] % mod;
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:54:30: warning: declaration of 'Y' shadows a global declaration [-Wshadow]
   54 | int init(int N, int X[], int Y[]) {
      |                          ~~~~^~~
horses.cpp:14:29: note: shadowed declaration is here
   14 | std :: vector<int> prod, X, Y;
      |                             ^
horses.cpp:54:21: warning: declaration of 'X' shadows a global declaration [-Wshadow]
   54 | int init(int N, int X[], int Y[]) {
      |                 ~~~~^~~
horses.cpp:14:26: note: shadowed declaration is here
   14 | std :: vector<int> prod, X, Y;
      |                          ^
horses.cpp:54:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   54 | int init(int N, int X[], int Y[]) {
      |          ~~~~^
horses.cpp:15:5: note: shadowed declaration is here
   15 | int N;
      |     ^
horses.cpp:55:6: warning: declaration of 'lg' shadows a global declaration [-Wshadow]
   55 |  int lg = 31 - __builtin_clz(N);
      |      ^~
horses.cpp:13:23: note: shadowed declaration is here
   13 | std :: vector<double> lg;
      |                       ^~

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