# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
154837 | junodeveloper | 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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int off=1<<19;
const int mod=1e9+7;
struct MULT {
int tree[off<<1];
MULT() {memset(tree,0,sizeof(tree));}
void update(int p,int x) {
p+=off;
tree[p]=x;p/=2;
while(p>0) {
tree[p]=(ll)tree[p<<1]*tree[p<<1|1]%mod;
p>>=1;
}
}
int query(int l,int r) {
int ret=1;
l+=off,r+=off;
while(l<r) {
if(l%2==1) ret=(ll)ret*tree[l++]%mod;
if(r%2==0) ret=(ll)ret*tree[r--]%mod;
l>>=1,r>>=1;
}
if(l==r) ret=(ll)ret*tree[l]%mod;
return ret;
}
} mult;
struct MAXT {
int tree[off<<1];
MAXT() {memset(tree,0,sizeof(tree));}
void update(int p,int x) {
p+=off;
tree[p]=x;p/=2;
while(p>0) {
tree[p]=max(tree[p<<1],tree[p<<1|1]);
p>>=1;
}
}
int query(int l,int r) {
int ret=0;
l+=off,r+=off;
while(l<r) {
if(l%2==1) ret=max(ret,tree[l++]);
if(r%2==0) ret=max(ret,tree[r--]);
l>>=1,r>>=1;
}
if(l==r) ret=max(ret,tree[l]);
return ret;
}
} maxt;
int n;
int *x, *y;
set<int> st;
int solve() {
auto it=st.end(); it--;
int i,j; ll r=1;
while(it!=st.begin()) {
r*=x[*it];
if(r>(ll)1e9) break;
it--;
}
int fir=*it;
r=1; ll mx=0;
while(it!=st.end()) {
i=*it;
if(next(it)==st.end()) j=n-1;
else j=*next(it)-1;
mx=max(mx,(ll)r*maxt.query(i,j));
it++; r*=x[i];
}
mx%=mod;
return (ll)mult.query(0,fir)*mx%mod;
}
int init(int N, int X[], int Y[]) {
n=N;
x=X,y=Y;
int i;
for(i=0;i<n;i++) {
mult.update(i,x[i]);
maxt.update(i,y[i]);
if(x[i]!=1) st.insert(i);
}
st.insert(0);
return solve();
}
int updateX(int pos, int val) {
if(pos&&x[pos]!=1) {
st.erase(pos);
}
x[pos]=val;
if(pos&&x[pos]!=1) {
st.insert(pos);
}
mult.update(pos,val);
return solve();
}
int updateY(int pos, int val) {
y[pos]=val;
maxt.update(pos,val);
return solve();
}