| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 343358 | bigDuck | 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>
using namespace std;
#define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
ll mod=((ll)1e9)+7;
int N;
ll exp(ll x, ll e){
if(e==1){
return x%mod;
}
if(e==0){
return 1;
}
return (exp(x, e%2)*exp( (x*x)%mod, e/2))%mod;
}
ll inv(ll x){
return exp(x, mod-2);
}
ll prod=1ll;
multiset<pii> suf;
int x[500010], y[500010];
int seg[2000010];
void build_seg(int v, int tl, int tr){
if(tl==tr){
seg[v]=y[tl];
return;
}
int mid=(tl+tr)>>1ll;
build_seg(2*v, tl, mid); build_seg(2*v+1, mid+1, tr);
seg[v]=max(seg[2*v], seg[2*v+1]);
return;
}
void update_seg(int v, int tl, int tr, int pos, int x){
if(tl==tr){
seg[v]=x;
y[tl]=x;
return;
}
int mid=(tl+tr)>>1ll;
if(pos<=mid){
update_seg(2*v, tl, mid, pos, x);
}
else{
update_seg(2*v+1, mid+1, tr, pos, x);
}
seg[v]=max(seg[2*v], seg[2*v+1]);
return;
}
int query(int v, int tl, int tr, int l, int r){
if(l>r){
return 0;
}
if( (tl==l) && (tr==r) ){
return seg[v];
}
int mid=(tl+tr)>>1ll;
int q1=query(2*v, tl, mid, l, min(r, mid)), q2=query(2*v+1, mid+1, tr, max(l, mid+1), r);
return max(q1, q2);
}
int get_resp(int N){
ll prod2=1ll;
ll prod3=1ll;
ll res=y[N];
auto it=suf.end();
ll lt=N;
if(it==suf.begin()){
res=query(1, 1, N, 1, lt);
return (res*prod)%mod;
}
it--;
int cnt=0;
for(;;it--){
ll pos=it->ft, X=it->sc;
ll Y=query(1, 1, N, pos, lt);
if( ( ( ( (res*prod3)%mod )*((prod2*inv(prod3))%mod ) ) )<Y ){
//cout<<res<<" "<<((res*prod2)%mod)<<" "<<Y<<" "<<prod<<"\n";
res=(Y*inv(prod2))%mod;
prod3=prod2;
cnt++;
}
lt=pos-1;
prod2*=X;
if(prod2>=((ll)1e9)){
break;
}
if(it==suf.begin()){
break;
}
}
if( ( ( ( (res*prod3)%mod )*((prod2*inv(prod3))%mod ) ) )<Y ){
//cout<<res<<" "<<((res*prod2)%mod)<<" "<<Y<<" "<<prod<<"\n";
res=(Y*inv(prod2))%mod;
prod3=prod2;
cnt++;
}
res=(res*prod)%mod;
return res;
}
int init(int n, int X[], int Y[]) {
//cout<<inv(1000000000ll)<<" "<<((1000000000ll*inv(1000000000ll))%mod )<<"\n";
N=n;
for(int i=1; i<=N; i++){
x[i]=X[i-1];
y[i]=Y[i-1];
}
build_seg(1, 1, N);
for(int i=1; i<=N; i++){
prod=(prod*x[i])%mod;
}
for(int i=1; i<=N; i++){
if(x[i]>1){
suf.insert({i, x[i]});
}
}
return get_resp(N);
}
int updateX(int pos, int val) {
auto it=suf.find(*suf.lower_bound({pos+1, 0}));
if( (it!=suf.end()) ){
if( (it->ft)==(pos+1) ){
prod=(prod*inv(it->sc))%mod;
suf.erase(it);
}
}
if( (val>1) ){suf.insert({(pos+1), val});}
prod=(prod*val)%mod;
return get_resp(N);
}
int updateY(int pos, int val) {
update_seg(1, 1, N, pos+1, val);
return get_resp(N);
}