| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1122036 | epicci23 | Horses (IOI15_horses) | C++17 | 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"
#include "horses.h"
using namespace std;
#define ll long long
#define all(x) x.begin(),x.end()
#define sz(x) (ll)x.size()
const ll N = 5e5 + 5;
const ll INF = 1e18 + 5;
const ll MOD = 1e9 + 7;
inline ll add(ll a,ll b){
a%=MOD,b%=MOD;
return (a+b)%MOD;
}
inline ll mult(ll a,ll b){
a%=MOD,b%=MOD;
return (a*b)%MOD;
}
inline ll fast(ll a,ll b,ll res=1){
for(;b;a=mult(a,a),b>>=1) if(b&1) res=mult(res,a);
return res;
}
inline ll inv(ll a){
return fast(a,MOD-2);
}
struct SegT{
vector<ll> seg;
SegT(ll _n){
seg.assign(4*_n+5,-INF);
}
void upd(ll rt,ll l,ll r,ll ind,ll u){
if(r<ind || l>ind) return;
if(l==r){
seg[rt]=u;
return;
}
ll mid=(l+r)/2;
upd(rt*2,l,mid,ind,u),upd(rt*2+1,mid+1,r,ind,u);
seg[rt]=max(seg[rt*2],seg[rt*2+1]);
}
ll query(ll rt,ll l,ll r,ll gl,ll gr){
if(r<gl || l>gr) return -INF;
if(l>=gl && r<=gr) return seg[rt];
ll mid=(l+r)/2;
return max(query(rt*2,l,mid,gl,gr),query(rt*2+1,mid+1,r,gl,gr));
}
};
ll fw[N],n;
set<ll> s;
SegT T(N,-INF);
array<ll,2> ar[N];
inline void upd(ll c,ll u){
for(;c<N;c+=c&-c) fw[c]=mult(fw[c],u);
}
inline ll query(ll c,ll res=1){
for(;c;c-=c&-c) res=mult(res,fw[c]);
return res;
}
inline ll find_ans(){
vector<ll> v;
/*set<ll>::reverse_iterator it = s.rbegin();
ll ekle = 1000;
while(ekle--){
if(it==s.rend()) break;
v.push_back(*it);
it++;
if(it==s.rend()) break;
}*/
for(ll i=n;i>=1;i--) v.push_back(i);
reverse(all(v));
ll m = sz(v);
vector<ll> g;
for(ll i = 0; i < m; i++) g.push_back(T.query(1,1,n,v[i],(i+1 == m ? n + 1 : v[i + 1]) - 1));
ll best = 0 , as = 1;
for(ll i = 1 ; i < m ;i++){
ll ind = v[i];
as *= ar[ind][0];
if(as > MOD || as * g[i] >= g[best]){
best = i;
as = 1;
}
}
return mult(g[best],query(v[best]));
}
int init(int nn, int X[], int Y[]){
n = nn;
for(ll i = 1 ; i <= n ; i++) ar[i][0] = X[i-1], ar[i][1] = Y[i-1];
fill(fw,fw+N,1);
for(ll i = 1 ; i <= n ; i++) upd(i,ar[i][0]);
s.insert(1);
for(ll i=2;i<=n;i++) if(ar[i][0] >= 2) s.insert(i);
for(ll i=1;i<=n;i++) T.upd(1,1,n,i,ar[i][1]);
return (int)find_ans();
}
int updateX(int pos, int val){
if(pos >= 2) s.erase(pos);
upd(pos,inv(ar[pos][0]));
ar[pos][0] = (ll) val;
if(pos >= 2 && val >= 2) s.insert(pos);
upd(pos,(ll)val);
return (int)find_ans();
}
int updateY(int pos, int val){
ar[(ll)pos][1] = (ll) val;
T.upd(1,1,n,(ll)pos,ar[(ll)pos][1]);
return (int)find_ans();
}
/*void _(){
cin >> n;
for(ll i = 1; i <= n ; i++) cin >> ar[i][0] >> ar[i][1];
fill(fw,fw+N,1);
for(ll i = 1 ; i <= n ; i++) upd(i,ar[i][0]);
for(ll i=1;i<=n;i++) if(ar[i][0] >= 2) s.insert(i);
for(ll i=1;i<=n;i++) T.upd(1,1,n,i,ar[i][1]);
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
ll tc=1;//cin >> tc;
while(tc--) _();
}*/