This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include "horses.h"
#include <cmath>
using namespace std;
int const MODULO = 1e9+7;
int n, bucketSize, bucketNum;
int const NMAX = 5e5;
int x[1 + NMAX];
int y[1 + NMAX];
int preX[1 + NMAX];
int sufX[1 + NMAX];
int const BMAX = 750;
int bbest[1 + BMAX];
int prod[1 + BMAX];
bool compare(int a, int b) {
if(b == -1 || a <= b) {
return true;
}
return false;
}
int multiply(int a, int b) {
if(a == -1 || b == -1 || (1LL * a * b >= MODULO )) {
return -1;
}
return (a * b);
}
void buildBucket(int index) {
int from = 1 + (index-1)*bucketSize, to = max(n, index*bucketSize);
int pre = 1, suf = 1;
prod[index] = 1;
for(int i = from;i <= to;i++) {
pre = multiply(pre, x[i]);
prod[index] = (1LL * prod[index] * x[i]) % MODULO;
preX[i] = pre;
}
for(int i = to;i >= from;i--) {
suf = multiply(suf, x[i]);
sufX[i] = suf;
}
int best = from, multBest = y[from], multAux = 1;
for(int i = from+1;i <= to;i++) {
multAux = multiply(multAux, x[i]);
if(compare(multBest, multiply(multAux, y[i]))) {
best = i;
multBest = y[best];
multAux = 1;
}
}
bbest[index] = best;
}
int computeSol() {
int best = bbest[1], multBest = y[bbest[1]], multAux = 1;
int prev = best;
for(int index = 2;index <= bucketNum;index++) {
int suf = 1, pre = 1;
if(prev % bucketSize != 0) {
suf = sufX[prev+1];
}
pre = preX[bbest[index]];
multAux = multiply(multAux, multiply(suf, pre));
if(compare(multBest, multiply(multAux, y[bbest[index]]))) {
best = bbest[index];
multBest = y[best];
multAux = 1;
}
prev = bbest[index];
}
int ans = 1, start = 1;
for(int index = 1;index * bucketSize < best;index++) {
ans = (1LL * ans * prod[index]) % MODULO;
start = index * bucketSize + 1;
}
for(int i = start;i <= best;i++) {
ans = (1LL * ans * x[i]) % MODULO;
}
ans = (1LL * ans * y[best]) % MODULO;
return ans;
}
int init(int N, int X[], int Y[]) {
n = N;
bucketSize = sqrt(n);
bucketNum = (n-1)/bucketSize+1;
for(int i = 1;i <= n;i++) {
x[i] = X[i-1];
y[i] = Y[i-1];
}
for(int i = 1;i <= bucketNum;i++) {
buildBucket(i);
}
return computeSol();
}
int updateX(int pos, int val) {
int bucketIndex = (pos-1)/bucketSize+1;
x[pos] = val;
buildBucket(bucketIndex);
return computeSol();
}
int updateY(int pos, int val) {
int bucketIndex = (pos-1)/bucketSize+1;
y[pos] = val;
buildBucket(bucketIndex);
return computeSol();
}
Compilation message (stderr)
horses.cpp: In function 'void buildBucket(int)':
horses.cpp:41:46: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
41 | prod[index] = (1LL * prod[index] * x[i]) % MODULO;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
horses.cpp: In function 'int computeSol()':
horses.cpp:79:37: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
79 | ans = (1LL * ans * prod[index]) % MODULO;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
horses.cpp:83:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
83 | ans = (1LL * ans * x[i]) % MODULO;
| ~~~~~~~~~~~~~~~~~~~^~~~~~~~
horses.cpp:85:31: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
85 | ans = (1LL * ans * y[best]) % MODULO;
| ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:91:20: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'int' may change value [-Wfloat-conversion]
91 | bucketSize = sqrt(n);
| ~~~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |