| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 121525 | nishkarsh | 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 <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pcc pair<char,char>
#define vi vector <int>
#define vl vector <ll>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d",x)
#define plld(x) printf("%lld",x)
#define pds(x) printf("%d ",x)
#define pllds(x) printf("%lld ",x)
#define pdn(x) printf("%d\n",x)
#define plldn(x) printf("%lld\n",x)
#define INF 2e9
#define INFLL 4e18
using namespace std;
ll powmod(ll base,ll exponent,ll mod){ // with mod < 1e9
ll ans=1;
while(exponent){
if(exponent&1)ans=(ans*base)%mod;
base=(base*base)%mod;
exponent/=2;
}
return ans;
}
ll gcd(ll a, ll b){
if(b==0) return a;
else return gcd(b,a%b);
}
const int upperlimit = 5e5+1;
const int mod = 1e9+7;
struct data
{
int last_ind=-1,maxy;
ll mult;
};
data merge(data a,data b){
data ans;
ans.mult=a.mult;ans.mult*=b.mult;
ans.mult%=mod;
if(b.last_ind==-1) ans.last_ind=a.last_ind;
else ans.last_ind=b.last_ind;
ans.maxy=max(a.maxy,b.maxy);
return ans;
}
data segtree[4*upperlimit];
int n;
ll ans;vi indices;
vi x;vi y;
void build(int node,int i,int j){
if(i==j){
segtree[node].mult=x[i];segtree[node].last_ind=i;segtree[node].maxy=y[i];
if(x[i]==1) segtree[node].last_ind=-1;
return;
}
int mid=(i+j)>>1;
build(2*node,i,mid);build(2*node+1,mid+1,j);
segtree[node]=merge(segtree[2*node],segtree[2*node+1]);
}
void update(int node,int i,int j,int ind,int val){
if(i==j){
segtree[node].mult=x[i];segtree[node].last_ind=i;segtree[node].maxy=y[i];
if(x[i]==1) segtree[node].last_ind=-1;
return;
}
int mid=(i+j)>>1;
if(ind<=mid) update(2*node,i,mid,ind,val);
else update(2*node+1,mid+1,j,ind,val);
segtree[node]=merge(segtree[2*node],segtree[2*node+1]);
}
data query(int node,int i,int j,int l,int r){
if((i>r)||(l>j)||(l>r)||(i>j)){
data unity;unity.mult=1;unity.maxy=0;unity.last_ind=-1;
return unity;
}
if((i>=l)&&(j<=r)) return segtree[node];
int mid=(i+j)>>1;
return merge(query(2*node,i,mid,l,r),query(2*node+1,mid+1,j,l,r));
}
int updateX(int pos,int val){
x[pos]=val;
update(1,0,n-1,pos,val);
int temp=n;
int ind=n-1;ll calc=y[n-1];
for(int i = 1; i <= 32; i++){
indices.pb(query(1,0,n-1,0,temp-1).last_ind);
temp=indices[indices.size()-1];
if(temp==-1) break;
int temp2=query(1,0,n-1,temp,n-1).maxy;
if(temp2>calc){
calc=temp2;
ind=temp;
}
calc*=x[temp];
if(calc>INF) break;
}
indices.clear();
ans=query(1,0,n-1,0,ind).mult;ans*=query(1,0,n-1,ind,n-1).maxy;
ans%=mod;
return ans;
}
int updateY(int pos,int val){
y[pos]=val;
update(1,0,n-1,pos,val);
int temp=n;
int ind=n-1;ll calc=y[n-1];
for(int i = 1; i <= 32; i++){
indices.pb(query(1,0,n-1,0,temp-1).last_ind);
temp=indices[indices.size()-1];
if(temp==-1) break;
int temp2=query(1,0,n-1,temp,n-1).maxy;
if(temp2>calc){
calc=temp2;
ind=temp;
}
calc*=x[temp];
if(calc>INF) break;
}
indices.clear();
ans=query(1,0,n-1,0,ind).mult;ans*=query(1,0,n-1,ind,n-1).maxy;
ans%=mod;
return ans;
}
int init(int N,vi X,vi Y){
n=N;
for(int i = 0; i < n; i++){
x.pb(X[i]);y.pb(Y[i]);
}
ll temp=Y[n-1];
int ind=n-1;
for(int i = n-1; i > 0; i--){
if(temp>INF) break;
temp*=X[i];
if(Y[i-1] > temp){
ind=i-1;temp=Y[i-1];
}
}
ans=Y[ind];
for(int i = 0; i <= ind; i++){
ans*=X[i];ans%=mod;
}
build(1,0,n-1);
return ans;
}