| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 154838 | junodeveloper | 말 (IOI15_horses) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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();
}