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<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+5;
const int mod = 1e9+7;
int st_max[4*maxn], st_prod[4*maxn];
int mult[maxn], cost[maxn];
int n;
void build(int X[], int Y[], int l = 0, int r = n-1, int id = 1){
if(l == r){
st_max[id] = Y[l];
st_prod[id] = X[l];
}
else {
int mid = (l+r)>>1;
build(X, Y, l, mid, id<<1);
build(X, Y, mid+1, r, id<<1|1);
st_max[id] = max(st_max[id<<1], st_max[id<<1|1]);
st_prod[id] = 1LL*st_prod[id<<1]*st_prod[id<<1|1]%mod;
}
}
void edit_max(int pos, int val, int l = 0, int r = n-1, int id = 1){
if(l == r)st_max[id] = val;
else {
int mid = (l+r)>>1;
if(pos <= mid)edit_max(pos, val, l, mid, id<<1);
else edit_max(pos, val, mid+1, r, id<<1|1);
st_max[id] = max(st_max[id<<1], st_max[id<<1|1]);
}
}
int get_max(int ql, int qr, int l = 0, int r = n-1, int id = 1){
if(ql > r || l > qr)return 0;
if(ql <= l && r <= qr)return st_max[id];
int mid = (l+r)>>1;
return max(get_max(ql, qr, l, mid, id<<1), get_max(ql, qr, mid+1, r, id<<1|1));
}
void edit_prod(int pos, int val, int l = 0, int r = n - 1, int id = 1){
if(l == r)st_prod[id] = val;
else {
int mid = (l+r)>>1;
if(pos <= mid)edit_prod(pos, val, l, mid, id<<1);
else edit_prod(pos, val, mid+1, r, id<<1|1);
st_prod[id] = 1LL*st_prod[id<<1]*st_prod[id<<1|1]%mod;
}
}
int get_prod(int ql, int qr, int l = 0, int r = n-1, int id = 1){
if(ql > r || l > qr)return 1;
if(ql <= l && r <= qr)return st_prod[id];
int mid = (l+r)>>1;
return 1LL*get_prod(ql, qr, l, mid, id<<1)*get_prod(ql, qr, mid+1, r, id<<1|1)%mod;
}
set<int> st;
int solve(){
int best = 0, bcost = 0, prv = n;
long long mx = 0;
for(auto it = st.rbegin(); it != st.rend(); it++){
int nw = get_max(*it, prv - 1);
// cout << nw << " " << mx << endl;
if(nw > mx){
mx = nw;
best = *it;
bcost = nw;
}
mx*=mult[*it];
if(mx >= mod)break;
}
return 1LL*get_prod(0, best)*bcost%mod;
}
int init(int N, int X[], int Y[]) {
n = N;
build(X, Y);
for(int i = 0; i < N; i++){
mult[i] = X[i];
cost[i] = Y[i];
if(X[i] > 1)st.insert(i);
}
st.insert(0);
return solve();
}
int updateX(int pos, int val) {
if(mult[pos] > 1)st.erase(pos);
mult[pos] = val;
edit_prod(pos, val);
if(mult[pos] > 1)st.insert(pos);
st.insert(0);
return solve();
}
int updateY(int pos, int val) {
cost[pos] = val;
edit_max(pos, val);
return solve();
}
Compilation message (stderr)
horses.cpp: In function 'void build(int*, int*, int, int, int)':
horses.cpp:24:52: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
24 | st_prod[id] = 1LL*st_prod[id<<1]*st_prod[id<<1|1]%mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'void edit_prod(int, int, int, int, int)':
horses.cpp:51:52: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
51 | st_prod[id] = 1LL*st_prod[id<<1]*st_prod[id<<1|1]%mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int get_prod(int, int, int, int, int)':
horses.cpp:59:80: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
59 | return 1LL*get_prod(ql, qr, l, mid, id<<1)*get_prod(ql, qr, mid+1, r, id<<1|1)%mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int solve()':
horses.cpp:79:36: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
79 | return 1LL*get_prod(0, best)*bcost%mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
# | 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... |