#include <bits/stdc++.h>
#include "horses.h"
#define ll long long
#define pb push_back
const ll mod = 1e9+7;
using namespace std;
int n;
ll maxV = 0;
ll acum[500005];
vector<ll>x, y;
set<int>doses;
int maximos[500000*4], posiciones[500000*4];
void merge(int node, int l, int r){
if(maximos[node*2] > maximos[node*2+1]){
maximos[node] = maximos[node*2];
posiciones[node] = posiciones[node*2];
}else{
maximos[node] = maximos[node*2+1];
posiciones[node] = posiciones[node*2+1];
}
}
void updateVal(int node, int l, int r, int pos, int value){
int temp = (l+r)/2;
if(l == r){
maximos[node] = value;
posiciones[node] = pos;
}else if(pos <= temp){
updateVal(node*2, l, temp, pos, value);
merge(node, l, r);
}else{
updateVal(node*2+1, temp+1, r, pos, value);
merge(node, l, r);
}
}
int queryMaximo(int node, int l, int r, int dd, int ht){
if(dd == l and ht == r)return posiciones[node];
int temp = (l + r ) /2;
if(ht <= temp)return queryMaximo(node*2, l, temp, dd, ht);
else if(dd > temp)return queryMaximo(node*2+1, temp+1, r, dd, ht);
else{
int m1 = queryMaximo(node*2, l, temp, dd, temp), m2 = queryMaximo(node*2+1, temp+1, r, temp+1, ht);
if(y[m1] > y[m2]){
return m1;
}else return m2;
}
}
int qq(int node, int l, int r, int dd , int ht){
if(dd > ht)return -1;
if ( dd == ht )return dd;
return queryMaximo(node, l, r, dd, ht);
}
ll fastExp(ll base, int pot){
if(pot == 0)return 1;
ll temp = fastExp(base, pot/2);
temp = temp * temp % mod;
if(pot % 2 == 1)temp = (temp * base) % mod;
return temp;
}
ll query(int pos){
ll ans = 1;
for(; pos>= 1 ; pos -= (pos&-pos)){
ans *= acum[pos];
ans %= mod;
}
return ans;
}
void multiplicar(int pos , int value){
for(; pos<= n ; pos += pos&(-pos)){
acum[pos] *= value;
acum[pos] %= mod;
}
}
void updateRet(){
ll ans = query(n) * y[n-1] % mod;
ll current = x[n-1]* y[n-1];
int curpos = n-1;
int realI;
for(auto i : doses){
realI = -i;
if(realI == n-1)continue;
int mm = qq(1, 0, n-1, i+1, curpos-1);
if(mm != -1){
if(y[mm] > current){
ans = query(mm+1) * y[mm] % mod;
current = x[mm]*y[mm];
}
}
if(current < y[realI]){
ans = query(realI+1) * y[realI] % mod;
current = x[realI]*y[realI];
}else{
current = current * x[realI];
}
curpos = realI;
}
/*
for(int i = n-2 ; i >= 0 ; i --){
if(current > 1e9){
maxV = ans;
return ;
}
if(current < y[i]){
ans = query(i+1) * y[i] % mod;
current = x[i]*y[i];
}else{
current = current * x[i];
}
}
*/
maxV = ans;
}
int init(int N, int X[], int Y[]) {
n = N;
for(int i = 0 ; i <= n ; i ++)acum[i] = 1;
for(int i = 0 ; i < N ; i++){
x.pb(X[i]);
y.pb(Y[i]);
multiplicar(i+1, X[i]);
updateVal(1, 0, N-1, i, Y[i]);
}
for(int i = n-1 ; i >=0 and doses.size() < 70 ; i --){
if(x[i] > 1)doses.insert(-i);
}
updateRet();
return maxV%mod;
}
int updateX(int pos, int val) {
multiplicar(pos + 1, fastExp(x[pos], mod-2));
if(x[pos] > 1 and val == 1 and doses.find(-pos) != doses.end())doses.erase(-pos);
else if(x[pos] == 1 and val > 1)doses.insert(-pos);
if(doses.size()==70)doses.erase(prev(doses.end()));
x[pos] = val;
multiplicar(pos + 1, x[pos]);
updateRet();
return maxV%mod;
}
int updateY(int pos, int val) {
y[pos] = val;
updateVal(1, 0, n-1, pos, val);
updateRet();
return maxV%mod;
}
Compilation message
horses.cpp: In function 'void merge(int, int, int)':
horses.cpp:16:26: warning: unused parameter 'l' [-Wunused-parameter]
16 | void merge(int node, int l, int r){
| ~~~~^
horses.cpp:16:33: warning: unused parameter 'r' [-Wunused-parameter]
16 | void merge(int node, int l, int r){
| ~~~~^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:132:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
132 | return maxV%mod;
| ~~~~^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:136:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
136 | multiplicar(pos + 1, fastExp(x[pos], mod-2));
| ~~~~~~~^~~~~~~~~~~~~~~
horses.cpp:141:29: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
141 | multiplicar(pos + 1, x[pos]);
| ^
horses.cpp:143:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
143 | return maxV%mod;
| ~~~~^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:150:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
150 | return maxV%mod;
| ~~~~^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Execution timed out |
1564 ms |
316 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
316 KB |
Output is correct |
| 2 |
Execution timed out |
1576 ms |
212 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1549 ms |
26492 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
312 KB |
Output is correct |
| 2 |
Execution timed out |
1577 ms |
212 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Execution timed out |
1575 ms |
320 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
