| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 210909 | autumn_eel | Horses (IOI15_horses) | C++14 | 0 ms | 0 KiB |
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>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
const int MOD=1000000007;
ll ppow(ll a,ll b){
ll res=1;
while(b){
if(b&1)res=(res*a)%MOD;
a=(a*a)%MOD;
b>>=1;
}
return res;
}
struct BIT{
vector<ll>bit;
BIT(){}
BIT(int n){
n=n+10;
bit=vector<ll>(n,1);
}
void add(int k,ll x){
k++;
while(k<bit.size()){
(bit[k]*=x)%=MOD;
k+=k&-k;
}
}
ll sum(int k){//[0,k)
ll res=1;
while(k){
(res*=bit[k])%=MOD;
k-=k&-k;
}
return res;
}
}bit;
struct Segtree{
int N;
vector<int>dat;
Segtree(){}
Segtree(int n){
N=1;while(N<n)N<<=1;
dat=vector<int>(2*N);
}
void update(int k,int x){
k+=N;dat[k]=x;
while(k>1){
k>>=1;
dat[k]=max(dat[k*2],dat[k*2+1]);
}
}
int query(int l,int r){
int res=0;
for(l+=N,r+=N;l<r;l>>=1,r>>=1){
if(l&1)res=max(res,dat[l++]);
if(r&1)res=max(res,dat[--r]);
}
return res;
}
}seg;
int n;
ll x[600000],y[600000];
set<int>se;
ll calc(){
if(se.empty())return seg.query(0,n)%MOD;
ll res=0;
ll M=1;
auto s=--se.end();
while(1){
M*=x[*s];
if(M>1e9||s==se.begin())break;
s--;
}
__int128 Max=0,cur=1;
for(auto it=s;it!=se.end();it++){
cur*=x[*it];
ll d=seg.query(*it,(it==--se.end()?n:*next(it)));
assert(log2(cur)+log2(d)<=100);
Max=max(Max,cur*d);
}
Max%=MOD;
Max*=bit.sum(*s);
return Max%MOD;
}
int init(int N, int X[], int Y[]) {
n=N;
bit=BIT(n);seg=Segtree(n);
rep(i,n){
x[i]=X[i],y[i]=Y[i];
bit.add(i,x[i]);
seg.update(i,y[i]);
if(x[i]>1)se.insert(i);
}
return (int)calc();
}
int updateX(int pos, int val) {
bit.add(pos,ppow(x[pos],MOD-2)*val%MOD);
if(val==1){
se.erase(pos);
}
else{
se.insert(pos);
}
x[pos]=val;
return (int)calc();
}
int updateY(int pos, int val) {
y[pos]=val;
seg.update(pos,val);
return (int)calc();
}