| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 64804 | Kubalionzzale | Horses (IOI15_horses) | C++14 | 0 ms | 0 KiB |
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 "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];
int getBetter(int one, int two)
{
long long int producted;
producted = queryMediumProduct(0, n - 1, one + 1, two, 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 constructProduct(int low, int high, int pos)
{
if (low == high)
{
product[pos] = x[low] * 1LL;
mediumProduct[pos] = x[low] * 1LL;
curBest[pos] = low;
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;
curBest[pos] = getBetter(curBest[pos * 2 + 1], curBest[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 updateProduct(int qpoint, int low, int high, int pos)
{
if (qpoint < low || qpoint > high)
return;
if (low == high)
{
product[pos] = x[low] * 1LL;
mediumProduct[pos] = x[low] * 1LL;
curBest[pos] = low;
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;
curBest[pos] = getBetter(curBest[pos * 2 + 1], curBest[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 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);
}
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;
}
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);
return (queryProduct(0, n - 1, 0, curBest[0], 0) * y[curBest[0]]) % mod;
}
int updateX(int position, int val) {
x[position] = val;
updateProduct(position, 0, n - 1, 0);
return (queryProduct(0, n - 1, 0, curBest[0], 0) * y[curBest[0]]) % mod;
}
int updateY(int position, int val) {
y[position] = val;
updateAnswer(position, 0, n - 1, 0);
return (queryProduct(0, n - 1, 0, curBest[0], 0) * y[curBest[0]]) % mod;
}