#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int lim = 1e9;
const int mod = 1e9 + 7;
const int mxN = 5e5 + 10;
int n;
int aX[mxN], aY[mxN];
pair<int, int> ST[mxN << 2];
map<int, int> mp;
void update(int node, int l, int r, int x) {
if(r < x || x < l) return ;
if(l == r) {
ST[node].first = aX[l];
ST[node].second = aY[l];
return ;
}
int mid = (l + r) / 2;
update(node * 2, l, mid, x);
update(node * 2 + 1, mid + 1, r, x);
ST[node].first = 1LL * (ST[node * 2].first * ST[node * 2 + 1].first) % mod;
ST[node].second = max(ST[node * 2].second, ST[node * 2 + 1].second);
}
int get_mul(int node, int l, int r, int x) {
if(l == r)
return ST[node].first;
int mid = (l + r) / 2;
if(x <= mid) {
return get_mul(node * 2, l, mid, x);
} else {
return 1LL * ST[node * 2].first * get_mul(node * 2 + 1, mid + 1, r, x) % mod;
}
}
int get_max(int node, int l, int r, int u, int v) {
if(r < u || v < l) return 0;
if(u <= l && r <= v)
return ST[node].second;
int mid = (l + r) / 2;
return max(get_max(node * 2, l, mid, u, v), get_max(node * 2 + 1, mid + 1, r, u, v));
}
int find_max() {
long double frmax = aY[n - 1];
int mul = 1;
int res = 1LL * get_mul(1, 0, n - 1, n - 1) * aY[n - 1] % mod;
for(auto i = mp.rbegin(); i != mp.rend(); ) {
int r = i->first;
r -- ;
if(1LL * mul * aX[i->first] > 1LL * lim) break ;
mul *= aX[i->first];
i ++ ;
if(i != mp.rend()) {
int l = i->first;
if(l > r) continue ;
int x = get_max(1, 0, n - 1, l, r);
long double frnew = (long double) x / mul;
if(frnew > frmax) {
frmax = frnew;
res = 1LL * get_mul(1, 0, n - 1, l) * x % mod;
}
}
}
return res;
}
int init(int N, vector<int> X, vector<int> Y) {
n = N;
for(int i = 0; i < N; i ++) aX[i] = X[i];
for(int i = 0; i < N; i ++) aY[i] = Y[i];
mp.insert({0, 1});
mp.insert({N - 1, 1});
for(int i = 0; i < N; i ++) {
if(aX[i] > 1) {
mp.insert({i, 1});
}
}
for(int i = 0; i < N; i ++) update(1, 0, N - 1, i);
return find_max();
}
int updateX(int pos, int val) {
aX[pos] = val;
update(1, 0, n - 1, pos);
if(pos != n - 1 && pos != 0 && aX[pos] <= 1) {
if(mp.find(pos) != mp.end()) {
mp.erase(pos);
}
}
if(aX[pos] > 1) mp.insert({pos, 1});
return find_max();
}
int updateY(int pos, int val) {
aY[pos] = val;
update(1, 0, n - 1, pos);
return find_max();
}
Compilation message
horses.cpp: In function 'int get_mul(int, int, int, int)':
horses.cpp:39:80: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
39 | return 1LL * ST[node * 2].first * get_mul(node * 2 + 1, mid + 1, r, x) % mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int find_max()':
horses.cpp:56:61: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
56 | int res = 1LL * get_mul(1, 0, n - 1, n - 1) * aY[n - 1] % mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:75:57: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
75 | res = 1LL * get_mul(1, 0, n - 1, l) * x % mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
/usr/bin/ld: /tmp/ccbPeNIT.o: in function `main':
grader.c:(.text.startup+0xaa): undefined reference to `init(int, int*, int*)'
collect2: error: ld returned 1 exit status
