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();
}
#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++; if(it!=st.end()) r*=x[*it];
}
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();
}
Compilation message (stderr)
horses.cpp:7:1: error: stray '\302' in program
^
horses.cpp:7:2: error: stray '\240' in program
^
horses.cpp:11:1: error: stray '\302' in program
^
horses.cpp:11:2: error: stray '\240' in program
^
horses.cpp:17:1: error: stray '\302' in program
^
horses.cpp:17:2: error: stray '\240' in program
^
horses.cpp:65:1: error: stray '\302' in program
^
horses.cpp:65:2: error: stray '\240' in program
^
horses.cpp:113:1: error: stray '\302' in program
^
horses.cpp:113:2: error: stray '\240' in program
^
horses.cpp:121:1: error: stray '\302' in program
^
horses.cpp:121:2: error: stray '\240' in program
^
horses.cpp:163:1: error: stray '\302' in program
^
horses.cpp:163:2: error: stray '\240' in program
^
horses.cpp:189:1: error: stray '\302' in program
^
horses.cpp:189:2: error: stray '\240' in program
^
horses.cpp:213:1: error: stray '\302' in program
^
horses.cpp:213:2: error: stray '\240' in program
^
horses.cpp:231:1: error: stray '\302' in program
^
horses.cpp:231:2: error: stray '\240' in program
^
horses.cpp:235:1: error: stray '\302' in program
^
horses.cpp:235:2: error: stray '\240' in program
^
horses.cpp:241:1: error: stray '\302' in program
^
horses.cpp:241:2: error: stray '\240' in program
^
horses.cpp:289:1: error: stray '\302' in program
^
horses.cpp:289:2: error: stray '\240' in program
^
horses.cpp:337:1: error: stray '\302' in program
^
horses.cpp:337:2: error: stray '\240' in program
^
horses.cpp:345:1: error: stray '\302' in program
^
horses.cpp:345:2: error: stray '\240' in program
^
horses.cpp:387:1: error: stray '\302' in program
^
horses.cpp:387:2: error: stray '\240' in program
^
horses.cpp:413:1: error: stray '\302' in program
^
horses.cpp:413:2: error: stray '\240' in program
^
horses.cpp:437:1: error: stray '\302' in program
^
horses.cpp:437:2: error: stray '\240' in program
^
horses.cpp: In member function 'void MULT::update(int, int)':
horses.cpp:33:39: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
tree[p]=(ll)tree[p<<1]*tree[p<<1|1]%mod;
~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In member function 'int MULT::query(int, int)':
horses.cpp:49:36: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
if(l%2==1) ret=(ll)ret*tree[l++]%mod;
~~~~~~~~~~~~~~~~~^~~~
horses.cpp:51:36: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
if(r%2==0) ret=(ll)ret*tree[r--]%mod;
~~~~~~~~~~~~~~~~~^~~~
horses.cpp:57:31: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
if(l==r) ret=(ll)ret*tree[l]%mod;
~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int solve()':
horses.cpp:159:33: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
return (ll)mult.query(0,fir)*mx%mod;
~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: At global scope:
horses.cpp:237:11: error: redefinition of 'const int off'
const int off=1<<19;
^~~
horses.cpp:13:11: note: 'const int off' previously defined here
const int off=1<<19;
^~~
horses.cpp:239:11: error: redefinition of 'const int mod'
const int mod=1e9+7;
^~~
horses.cpp:15:11: note: 'const int mod' previously defined here
const int mod=1e9+7;
^~~
horses.cpp:243:8: error: redefinition of 'struct MULT'
struct MULT {
^~~~
horses.cpp:19:8: note: previous definition of 'struct MULT'
struct MULT {
^~~~
horses.cpp:287:3: error: conflicting declaration 'int mult'
} mult;
^~~~
horses.cpp:63:3: note: previous declaration as 'MULT mult'
} mult;
^~~~
horses.cpp:291:8: error: redefinition of 'struct MAXT'
struct MAXT {
^~~~
horses.cpp:67:8: note: previous definition of 'struct MAXT'
struct MAXT {
^~~~
horses.cpp:335:3: error: conflicting declaration 'int maxt'
} maxt;
^~~~
horses.cpp:111:3: note: previous declaration as 'MAXT maxt'
} maxt;
^~~~
horses.cpp:339:5: error: redefinition of 'int n'
int n;
^
horses.cpp:115:5: note: 'int n' previously declared here
int n;
^
horses.cpp:341:6: error: redefinition of 'int* x'
int *x, *y;
^
horses.cpp:117:6: note: 'int* x' previously declared here
int *x, *y;
^
horses.cpp:341:10: error: redefinition of 'int* y'
int *x, *y;
^
horses.cpp:117:10: note: 'int* y' previously declared here
int *x, *y;
^
horses.cpp:343:10: error: redefinition of 'std::set<int> st'
set<int> st;
^~
horses.cpp:119:10: note: 'std::set<int> st' previously declared here
set<int> st;
^~
horses.cpp: In function 'int solve()':
horses.cpp:347:5: error: redefinition of 'int solve()'
int solve() {
^~~~~
horses.cpp:123:5: note: 'int solve()' previously defined here
int solve() {
^~~~~
horses.cpp:383:33: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
return (ll)mult.query(0,fir)*mx%mod;
~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:389:5: error: redefinition of 'int init(int, int*, int*)'
int init(int N, int X[], int Y[]) {
^~~~
horses.cpp:165:5: note: 'int init(int, int*, int*)' previously defined here
int init(int N, int X[], int Y[]) {
^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:415:5: error: redefinition of 'int updateX(int, int)'
int updateX(int pos, int val) {
^~~~~~~
horses.cpp:191:5: note: 'int updateX(int, int)' previously defined here
int updateX(int pos, int val) {
^~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:439:5: error: redefinition of 'int updateY(int, int)'
int updateY(int pos, int val) {
^~~~~~~
horses.cpp:215:5: note: 'int updateY(int, int)' previously defined here
int updateY(int pos, int val) {
^~~~~~~