Submission #126405

#	Time	Username	Problem	Language	Result	Execution time	Memory
126405		KieranHorgan	Horses (IOI15_horses)	C++17	0 / 100	61 ms	25096 KiB

horses

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

const int MOD = 1000000007;
#define ll long long

int n;
vector<int> Y_;
vector<int> X_;
vector<ll> st;
ll op(ll a, ll b) {
	return (a*b)%MOD;
}
void build(int id = 1, int l = 0, int r = n) {
	if(l+1==r) {
		st[id] = X_[l];
		return;
	}
	int mid = (l+r)>>1;
	build(id<<1, l, mid);
	build((id<<1) | 1, mid, r);
	st[id] = op(st[id<<1], st[(id<<1)|1]);
	return;
}
void update(int pos, int val, int id = 1, int l = 0, int r = n) {
	if(pos >= r || pos < l) return;
	if(l+1 == r) {
		X_[pos] = val;
		st[id] = val;
		return;
	}
	int mid = (l+r)/2;
	update(pos, val, id<<1, l, mid);
	update(pos, val, (id<<1)|1, mid, r);
	st[id] = op(st[id<<1], st[(id<<1)|1]);
}
int query(int pos, int id = 1, int l = 0, int r = n) {
	if(pos >= r-1) return st[id];
	if(pos < l) return 1;
	int mid = (l+r)/2;
	return op(query(pos, id<<1, l, mid),
			  query(pos, (id<<1)|1, mid, r));
}

int calcBestPos() {
	int i = max(0, n-20);
	int curBest = Y_[i];
	int curBestPos = i;
	int run = X_[i];
	for(i++; i < n; i++) {
		if(run * Y_[i] * X_[i] >= curBest) {
			run = 1;
			curBest = Y_[i] * X_[i];
			curBestPos = i;
		} else {
			run *= X_[i];
		}
	}
	return curBestPos;
}

int init(int N, int X[], int Y[]) {
	n = N;
	for(int i = 0; i < n; i++) {
		X_.push_back(X[i]);
		Y_.push_back(Y[i]);
	}
	st.resize(3*n+5);
	build();
	int p = calcBestPos();
	return op(query(p), Y_[p]);
}

int updateX(int pos, int val) {	
	update(pos,val);
	int p = calcBestPos();
	return op(query(p), Y_[p]);
}

int updateY(int pos, int val) {
	Y_[pos] = val;
	int p = calcBestPos();
	return op(query(p), Y_[p]);
}

Compilation message (stderr)

horses.cpp: In function 'int query(int, int, int, int)':
horses.cpp:39:29: warning: conversion to 'int' from '__gnu_cxx::__alloc_traits<std::allocator<long long int> >::value_type {aka long long int}' may alter its value [-Wconversion]
  if(pos >= r-1) return st[id];
                             ^
horses.cpp:42:11: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return op(query(pos, id<<1, l, mid),
         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
      query(pos, (id<<1)|1, mid, r));
      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:72:11: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return op(query(p), Y_[p]);
         ~~^~~~~~~~~~~~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:78:11: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return op(query(p), Y_[p]);
         ~~^~~~~~~~~~~~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:84:11: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return op(query(p), Y_[p]);
         ~~^~~~~~~~~~~~~~~~~

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