#include "horses.h"
#include <algorithm>
int n;
long long int mod = 1e9 + 7;
long long int product[2000010] = { 0 };
long long int mediumProduct[2000010] = { 0 };
int curBest[2000010] = { 0 };
int x[500010], y[500010];
void constructProduct(int low, int high, int pos)
{
if (low == high)
{
product[pos] = x[low] * 1LL;
return;
}
int mid = low + (high - low) / 2;
constructProduct(low, mid, pos * 2 + 1);
constructProduct(mid + 1, high, pos * 2 + 2);
product[pos] = (product[pos * 2 + 1] * product[pos * 2 + 2]) % mod;
}
void updateProduct(int qpoint, int low, int high, int pos)
{
if (qpoint < low || qpoint > high)
return;
if (low == high)
{
product[pos] = x[low] * 1LL;
return;
}
int mid = low + (high - low) / 2;
updateProduct(qpoint, low, mid, pos * 2 + 1);
updateProduct(qpoint, mid + 1, high, pos * 2 + 2);
product[pos] = (product[pos * 2 + 1] * product[pos * 2 + 2]) % mod;
}
long long int queryProduct(int low, int high, int qlow, int qhigh, int pos)
{
if (high < qlow || low > qhigh)
return 1;
if (qlow <= low && high <= qhigh)
{
return product[pos];
}
int mid = low + (high - low) / 2;
return ((queryProduct(low, mid, qlow, qhigh, pos * 2 + 1) * queryProduct(mid + 1, high, qlow, qhigh, pos * 2 + 2)) % mod);
}
void constructMediumProduct(int low, int high, int pos)
{
if (low == high)
{
mediumProduct[pos] = x[low] * 1LL;
return;
}
int mid = low + (high - low) / 2;
constructMediumProduct(low, mid, pos * 2 + 1);
constructMediumProduct(mid + 1, high, pos * 2 + 2);
long long int val = mediumProduct[pos * 2 + 1] * mediumProduct[pos * 2 + 2];
if (val > 1e9)
mediumProduct[pos] = 0;
else
mediumProduct[pos] = val;
}
void updateMediumProduct(int qpoint, int low, int high, int pos)
{
if (qpoint < low || qpoint > high)
return;
if (low == high)
{
mediumProduct[pos] = x[low] * 1LL;
return;
}
int mid = low + (high - low) / 2;
constructMediumProduct(low, mid, pos * 2 + 1);
constructMediumProduct(mid + 1, high, pos * 2 + 2);
long long int val = mediumProduct[pos * 2 + 1] * mediumProduct[pos * 2 + 2];
if (val > 1e9)
mediumProduct[pos] = 0;
else
mediumProduct[pos] = val;
}
long long int queryMediumProduct(int low, int high, int qlow, int qhigh, int pos)
{
if (high < qlow || low > qhigh)
return 1;
if (qlow <= low && high <= qhigh)
{
return mediumProduct[pos];
}
int mid = low + (high - low) / 2;
long long int val1 = queryMediumProduct(low, mid, qlow, qhigh, pos * 2 + 1);
long long int val2 = queryMediumProduct(mid + 1, high, qlow, qhigh, pos * 2 + 2);
if (val1 * val2 > 1e9)
return 0;
else
return val1 * val2;
}
int getBetter(int one, int two)
{
long long int producted;
if (two - one == 1)
producted = 1;
else
producted = queryMediumProduct(0, n - 1, one + 1, two - 1, 0);
if (producted == 0)
return two;
else
{
long double oneans = y[one];
long double twoans = producted * y[two];
if (oneans > twoans)
return one;
else
return two;
}
}
void constructAnswer(int low, int high, int pos)
{
if (low == high)
{
curBest[pos] = low;
return;
}
int mid = low + (high - low) / 2;
constructAnswer(low, mid, pos * 2 + 1);
constructAnswer(mid + 1, high, pos * 2 + 2);
curBest[pos] = getBetter(curBest[pos * 2 + 1], curBest[pos * 2 + 2]);
}
void updateAnswer(int qpoint, int low, int high, int pos)
{
if (qpoint < low || qpoint > high)
return;
if (low == high)
{
curBest[pos] = low;
return;
}
int mid = low + (high - low) / 2;
updateAnswer(qpoint, low, mid, pos * 2 + 1);
updateAnswer(qpoint, mid + 1, high, pos * 2 + 2);
curBest[pos] = getBetter(curBest[pos * 2 + 1], curBest[pos * 2 + 2]);
}
int init(int N, int inx[], int iny[]) {
n = N;
for (int i = 0; i < n; ++i)
{
x[i] = inx[i];
y[i] = iny[i];
}
constructProduct(0, n - 1, 0);
constructMediumProduct(0, n - 1, 0),
constructAnswer(0, n - 1, 0);
return curBest[0];
}
int updateX(int position, int val) {
x[position] = val;
updateProduct(position, 0, n - 1, 0);
updateMediumProduct(position, 0, n - 1, 0);
updateAnswer(position, 0, n - 1, 0);
return curBest[0];
}
int updateY(int position, int val) {
updateAnswer(position, 0, n - 1, 0);
return curBest[0];
}
Compilation message
horses.cpp: In function 'void constructMediumProduct(int, int, int)':
horses.cpp:77:15: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
if (val > 1e9)
^~~
horses.cpp: In function 'void updateMediumProduct(int, int, int, int)':
horses.cpp:101:15: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
if (val > 1e9)
^~~
horses.cpp: In function 'long long int queryMediumProduct(int, int, int, int, int)':
horses.cpp:122:14: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
if (val1 * val2 > 1e9)
~~~~~^~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:212:31: warning: unused parameter 'val' [-Wunused-parameter]
int updateY(int position, int val) {
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
519 ms |
29476 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
29476 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
29476 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
