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 <bits/stdc++.h>
#define LL long long
#define F first
#define S second
using namespace std;
const int M = 5e5+10;
const int MOD = 1e9+7;
LL add(LL a,LL b){
return (a+b)%MOD;
}
LL mult(LL a,LL b){
return (a*b)%MOD;
}
LL fastpow(LL n,LL k){
LL ret = 1;
while(k){
if(k&1)ret = mult(ret,n);
k /= 2;
n = mult(n,n);
}
return ret;
}
LL divide(LL a,LL b){
return mult(a,fastpow(b,MOD-2));
}
LL a[M],b[M],tree[M*4][2],n;
LL pr = 1;
set<int>st;
void update(int v,int tl,int tr,int pos,int val,int t){
if(tl==tr){
tree[v][t] = val;
return ;
}
int mid = (tl+tr)/2;
if(pos<=mid)
update(v*2,tl,mid,pos,val,t);
else
update(v*2+1,mid+1,tr,pos,val,t);
if(!t)
tree[v][t] = max(tree[v*2][t],tree[v*2+1][t]);
else
tree[v][t] = mult(tree[v*2][t],tree[v*2+1][t]);
}
LL get(int v,int tl,int tr,int l,int r,int t){
if(tl>r||tr<l)
return 1;
if(tl>=l&&tr<=r)
return tree[v][t];
int mid = (tl+tr)/2;
if(!t)
return max(get(v*2,tl,mid,l,r,t),get(v*2+1,mid+1,tr,l,r,t));
else
return mult(get(v*2,tl,mid,l,r,t),get(v*2+1,mid+1,tr,l,r,t));
}
LL calc(){
vector<pair<LL,LL>>vec;
int cnt = 0,last = n+1;
for(auto it:st){
if(cnt==30)
break;
cnt++;
int idx = -(it);
if(last-idx>1)
vec.push_back({1,get(1,1,n,idx+1,last-1,0)});
last = idx;
vec.push_back({a[idx],b[idx]});
}
pr = (last==1)?1:get(1,1,n,1,last-1,1);
if(vec.empty())
vec.push_back({1,get(1,1,n,1,n,0)});
reverse(vec.begin(),vec.end());
LL idx = 0,cur = 1;
for(int i = 1;i<vec.size();i++){
if((cur*vec[i].F>vec[idx].S)||(cur*vec[i].F*vec[i].S>vec[idx].S))
idx = i,cur = 1;
else
cur *= vec[i].F;
}
cur = 1;
for(int i=0;i<=idx;i++)
cur = mult(cur,vec[i].F);
return mult(pr,mult(cur,vec[idx].S));
}
int init(int N, int X[], int Y[]) {
n = N;
a[0] = 1;
st.insert(0);
for(int i=1;i<=n;i++){
a[i] = X[i-1];
b[i] = Y[i-1];
update(1,1,n,i,b[i],0);
update(1,1,n,i,a[i],1);
if(a[i]>1)
st.insert(-i);
}
return calc();
}
int updateX(int pos, int val) {
if(a[pos+1]>1)
st.erase(-pos-1);
a[pos+1] = val;
update(1,1,n,pos+1,val,1);
if(a[pos+1]>1)
st.insert(-pos-1);
return calc();
}
int updateY(int pos, int val) {
b[pos+1] = val;
update(1,1,n,pos+1,b[pos+1],0);
return calc();
}
Compilation message (stderr)
horses.cpp: In function 'long long int calc()':
horses.cpp:77:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
77 | int cnt = 0,last = n+1;
| ~^~
horses.cpp:85:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
85 | vec.push_back({1,get(1,1,n,idx+1,last-1,0)});
| ^
horses.cpp:90:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
90 | pr = (last==1)?1:get(1,1,n,1,last-1,1);
| ^
horses.cpp:93:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
93 | vec.push_back({1,get(1,1,n,1,n,0)});
| ^
horses.cpp:93:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
93 | vec.push_back({1,get(1,1,n,1,n,0)});
| ^
horses.cpp:97:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int i = 1;i<vec.size();i++){
| ~^~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:120:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
120 | update(1,1,n,i,b[i],0);
| ^
horses.cpp:120:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
120 | update(1,1,n,i,b[i],0);
| ~~~^
horses.cpp:121:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
121 | update(1,1,n,i,a[i],1);
| ^
horses.cpp:121:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
121 | update(1,1,n,i,a[i],1);
| ~~~^
horses.cpp:127:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
127 | return calc();
| ~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:136:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
136 | update(1,1,n,pos+1,val,1);
| ^
horses.cpp:141:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
141 | return calc();
| ~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:147:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
147 | update(1,1,n,pos+1,b[pos+1],0);
| ^
horses.cpp:147:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
147 | update(1,1,n,pos+1,b[pos+1],0);
| ~~~~~~~^
horses.cpp:149:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
149 | return calc();
| ~~~~^~
# | 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... |