Submission #393533

#	Time	Username	Problem	Language	Result	Execution time	Memory
393533		bigg	Horses (IOI15_horses)	C++14	17 / 100	44 ms	16900 KiB

horses

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

typedef long long ll;
const int MAXN = 5e5 + 10;
const ll MOD = 1e9 + 7;

ll prefx[MAXN], y[MAXN], x[MAXN];
int n;


ll exp(ll a, ll e){
	if(e == 0) return 1;
	if(e == 1) return a;
	ll ans = exp(a, e/2)%MOD;
	(ans*=ans)%=MOD;
	if(e%2) (ans*=a)%=MOD;
	return ans;
}

int init(int N, int X[], int Y[]) {
	n = N;
	for(int i = 0; i < N; i++){
		x[i] = X[i];
		y[i] = Y[i];
		prefx[i] = X[i];
		if(i) (prefx[i]*=prefx[i-1])%=MOD;
	}
	ll ans = 0;
	for(int i = max(0,n-31); i < n; i++){
		ans = max(ans,  (prefx[i]*y[i])%MOD);
	}
	return ans;
}

int updateX(int pos, int val) {

	ll v = val;

	if(n-pos > 32 ){
		for(int i = n-31; i < n; i++ ){
			(prefx[i] *= exp(x[pos], MOD - 2))%=MOD;
			prefx[i] *= v;
			prefx[i]%=MOD;
		}
	}else{
		for(int i = pos; i < n; i++){
			(prefx[i] *= exp(x[pos], MOD - 2))%=MOD;
			prefx[i] *= v;
			prefx[i]%=MOD;
		}
	}
	ll ans = 0;
	for(int i = max(0,n-31); i < n; i++){
		ans = max(ans,  (prefx[i]*y[i])%MOD);
	}
	x[pos] = val;
	return ans;
	
}

int updateY(int pos, int val) {
	y[pos] = val;
	ll ans = 0;
	for(int i = max(0,n-31); i < n; i++){
		ans = max(ans,  (prefx[i]*y[i])%MOD);
	}
	return ans;
	
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:34:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   34 |  return ans;
      |         ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:59:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   59 |  return ans;
      |         ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:69:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   69 |  return ans;
      |         ^~~

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