이 제출은 이전 버전의 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));
r*=x[i]; 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();
}
컴파일 시 표준 에러 (stderr) 메시지
horses.cpp: In member function 'void MULT::update(int, int)':
horses.cpp:17: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:25: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:26: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:29: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:80:33: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
return (ll)mult.query(0,fir)*mx%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... |