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 <set>
#include <vector>
#include <algorithm>
const int YMAX = 1e9;
const int MOD = 1e9 + 7;
const int NMAX = 5e5;
int n, x[NMAX + 2], y[NMAX + 2];
struct Aintx {
int v[4 * NMAX];
void Build(int node, int st, int dr)
{
if(st == dr)
{
v[node] = x[st];
return ;
}
int mid = (st + dr) >> 1;
Build(2 * node, st, mid);
Build(2 * node + 1, mid + 1, dr);
v[node] = (1LL * v[2 * node] * v[2 * node + 1]) % MOD;
}
void setx(int node, int st, int dr, int pos, int val)
{
if(st == dr)
{
v[node] = val;
return;
}
int mid = (st + dr) >> 1;
if(pos <= mid)
setx(2 * node, st, mid, pos, val);
else
setx(2 * node + 1, mid + 1, dr, pos, val);
v[node] = (1LL * v[2 * node] * v[2 * node + 1]) % MOD;
}
int queryx(int node, int st, int dr, int l, int r)
{
if(st > dr)
return 0;
if(l <= st && dr <= r)
return v[node];
if(dr < l || st > r)
return 1;
int mid = (st + dr) >> 1;
int ans1 = queryx(2 * node, st, mid, l, r);
int ans2 = queryx(2 * node + 1, mid + 1, dr, l, r);
return (1LL * ans1 * ans2) % MOD;
}
};
Aintx aintx;
struct Ainty {
int v[4 * NMAX];
void Build(int node, int st, int dr)
{
if(st == dr)
{
v[node] = y[st];
return ;
}
int mid = (st + dr) >> 1;
Build(2 * node, st, mid);
Build(2 * node + 1, mid + 1, dr);
v[node] = std::max(v[2 * node], v[2 * node + 1]);
}
void sety(int node, int st, int dr, int pos, int val)
{
if(st == dr)
{
v[node] = val;
return;
}
int mid = (st + dr) >> 1;
if(pos <= mid)
sety(2 * node, st, mid, pos, val);
else
sety(2 * node + 1, mid + 1, dr, pos, val);
v[node] = std::max(v[2 * node], v[2 * node + 1]);
}
int queryy(int node, int st, int dr, int l, int r)
{
if(st > dr)
return 0;
if(l <= st && dr <= r)
return v[node];
if(dr < l || st > r)
return 0;
int mid = (st + dr) >> 1;
int ans1 = queryy(2 * node, st, mid, l, r);
int ans2 = queryy(2 * node + 1, mid + 1, dr, l, r);
return std::max(ans1, ans2);
}
};
Ainty ainty;
std::set <int> s;
int Query()
{
if(s.size() == 0)
return ainty.queryy(1, 0, n - 1, 0, n - 1);
long long prod = 1LL;
std::vector <int> pos;
for(auto it : s)
{
pos.push_back(-it);
prod *= x[-it];
if(prod >= YMAX)
break;
}
int sz = (int)pos.size();
long long px = 1LL, mx = 1LL, py;
for(int i = sz - 2; i >= 0; i--)
{
px *= x[pos[i]];
if(i)
py = ainty.queryy(1, 0, n - 1, pos[i], pos[i - 1] - 1);
else
py = ainty.queryy(1, 0, n - 1, pos[i], n - 1);
mx = std::max(mx, px * py);
}
return (1LL * mx * aintx.queryx(1, 0, n - 1, 0, pos[sz - 1]));
}
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];
aintx.Build(1, 0, n - 1);
ainty.Build(1, 0, n - 1);
for(int i = 0; i < n; i++) {
if(x[i] > 1) {
s.insert(-i);
}
}
return Query();
}
int updateX(int pos, int val) {
if(x[pos] == val)
return Query();
aintx.setx(1, 0, n - 1, pos, val);
if(x[pos] > 1 && val == 1)
s.erase(-pos);
else if(x[pos] == 1 && val > 1)
s.insert(-pos);
x[pos] = val;
return Query();
}
int updateY(int pos, int val) {
if(y[pos] == val)
return Query();
ainty.sety(1, 0, n - 1, pos, val);
y[pos] = val;
return Query();
}
Compilation message (stderr)
horses.cpp: In member function 'void Aintx::Build(int, int, int)':
horses.cpp:28:61: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
28 | v[node] = (1LL * v[2 * node] * v[2 * node + 1]) % MOD;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'void Aintx::setx(int, int, int, int, int)':
horses.cpp:45:61: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
45 | v[node] = (1LL * v[2 * node] * v[2 * node + 1]) % MOD;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'int Aintx::queryx(int, int, int, int, int)':
horses.cpp:63:40: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
63 | return (1LL * ans1 * ans2) % MOD;
| ~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int Query()':
horses.cpp:157:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
157 | return (1LL * mx * aintx.queryx(1, 0, n - 1, 0, pos[sz - 1]));
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |