이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long
using namespace std;
int n, tr[2000000], id[500001];
ll bit[500001];
ll now=1;
vector<int>x, y;
set<int>a;
void update(int ind, int val){
while(ind<=500000){
bit[ind]*=val;
bit[ind]%=mod;
ind+=ind&-ind;
}
}
ll get(int ind){
if(ind<0) return 1;
ll ans=1;
while(ind>0){
ans*=bit[ind];
ans%=mod;
ind-=ind&-ind;
}
return ans;
}
void pre(){
fill(bit, bit+500001, 1);
a.insert(-1);
a.insert(0);
for(int i=0; i<n; i++){
if(x[i]>1){
a.insert(i);
update(i+1, x[i]);
}
}
}
void build(int ind, int l, int r){
if(l==r){
tr[ind]=y[l];
id[l]=ind;
return;
}
build(ind*2, l, (l+r)/2);
build(ind*2+1, (l+r)/2+1, r);
tr[ind]=max(tr[ind*2], tr[ind*2+1]);
}
void upd(int ind){
if(ind==0) return;
tr[ind]=max(tr[ind*2], tr[ind*2+1]);
upd(ind/2);
}
ll rmq(int ind, int l, int r, int L, int R){
if(l==L && r==R) return tr[ind];
int m=(l+r)/2;
if(R<=m) return rmq(ind*2, l, m, L, R);
else if(L>m) return rmq(ind*2+1, m+1, r, L, R);
else{
return max(rmq(ind*2, l, m, L, m), rmq(ind*2+1, m+1, r, m+1, R));
}
}
ll find(){
ll ans=1;
ll now=rmq(1, 0, n-1, *prev(a.end()), n-1);
set<int>::iterator it;
for(it=prev(a.end()); it!=a.begin() && now<mod; it--){
if(now*x[*it]>=mod) {
it++;
break;
}
now*=x[*it];
}
ans=now;
now/=rmq(1, 0, n-1, *prev(a.end()), n-1);
for(set<int>::iterator tmp=prev((prev(a.end()))); tmp!=prev(it) && tmp!=a.begin(); tmp--){
now/=x[*next(tmp)];
ans=max(ans, now*rmq(1, 0, n-1, *tmp, *next(tmp)-1));
}
ans%=mod;
if(it!=a.begin()) ans*=get(*next(it)+1);
ans%=mod;
ll res=1;
/*for(; it!=a.begin(); it--){
cout << x[*it] << " " ;
ans*=x[*it];
res*=x[*it];
res%=mod;
ans%=mod;
}*/
return ans;
}
int init(int N, int X[], int Y[]) {
n=N;
for(int i=0; i<n; i++) {x.push_back(X[i]); y.push_back(Y[i]);}
pre();
build(1, 0, n-1);
return find();
}
ll pw(ll o, ll p){
if(p==0) return 1;
ll ans=pw(o, p/2);
ans*=ans;
ans%=mod;
if(p%2) ans*=o;
ans%=mod;
return ans;
}
int updateX(int pos, int val){
if(x[pos]==1 && val==1) return find();
if(x[pos]>1 && val>1){
update(pos+1, pw(x[pos], mod-2));
update(pos+1, val);
x[pos]=val;
return find();
}
if(x[pos]==1){
a.insert(pos);
update(pos+1, val);
x[pos]=val;
}
else{
a.erase(pos);
update(pos+1, pw(x[pos], mod-2));
x[pos]=1;
}
return find();
}
int updateY(int pos, int val){
tr[id[pos]]=val;
upd(id[pos]/2);
return find();
}
컴파일 시 표준 에러 (stderr) 메시지
horses.cpp: In function 'long long int find()':
horses.cpp:73:8: warning: declaration of 'now' shadows a global declaration [-Wshadow]
ll now=rmq(1, 0, n-1, *prev(a.end()), n-1);
^~~
horses.cpp:9:4: note: shadowed declaration is here
ll now=1;
^~~
horses.cpp:91:8: warning: unused variable 'res' [-Wunused-variable]
ll res=1;
^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:107:16: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return find();
~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:121:40: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
if(x[pos]==1 && val==1) return find();
~~~~^~
horses.cpp:123:25: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
update(pos+1, pw(x[pos], mod-2));
~~^~~~~~~~~~~~~~~
horses.cpp:126:20: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return find();
~~~~^~
horses.cpp:135:25: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
update(pos+1, pw(x[pos], mod-2));
~~^~~~~~~~~~~~~~~
horses.cpp:138:16: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return find();
~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:144:16: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return find();
~~~~^~
# | 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... |