| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 225544 | nickmet2004 | 말 (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 "horses.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e5 + 5 , mod = 1e9 + 7;
int n;
vector<int> x , y;
int xmult;
set<int> poss;
int T[1 << 20];
ll pow(ll a , ll p){
inline ll Inv(ll a) {return pow(a % mod, mod - 2);}
void upd(int idx , int v , int l = 0 , int r = n - 1 , int pos = 1){
if(l == r){
T[pos] = v;return;
}
int mid = (l + r) >> 1;
if(idx <= mid) upd(idx , v , l , mid , pos * 2);
else upd(idx , v , mid + 1 , r , pos * 2 + 1);
T[pos] = max(T[pos* 2] , T[pos *2 + 1]);
}
int get(int L , int R , int l = 0 , int r= n - 1 , int pos =1){
if(r < L || R < l) return INT_MIN;
if(L <= l && r <= R) return T[pos];
int mid = (l + r) >> 1;
return max(get(L , R , l , mid , pos * 2) , get(L , R , mid + 1 , r , pos * 2 + 1));
}
struct div{
ll a , b;
};
inline bool operator<(div l , div r){return l.a * r.b < r.a * l.b;}
int solve(){
div mx{0 , 1};
ll curxmult = 1;
/// (y / curxmult) has to be as large as possible
for(auto it = poss.rbegin(); it != poss.rend() && curxmult < 1000000000LL; ++it){
int i = *it;
int j = (it == poss.rbegin() ? n : *prev(it));
mx = max(mx , {get(i , j - 1) , curxmult});
curxmult *= x[i];
}
ll res = (mx.a * Inv(mx.b)) % mod;
return res = (res * xmult) % mod;
}
int init(int N , int X[] , int Y[]){
n = N;
x.assign(X , X + N);
y.assign(Y , Y + N);
for(int i = 0; i < n; ++i){
upd(i , y[i]);
}
poss.clear();
xmult = 1;
poss.insert(0);
for(int i = 0; i < n; ++i){
if(x[i] > 1){
poss.insert(i);
xmult = (xmult * x[i]) % mod;
}
}
return solve();
}
int updateX(int pos , int val){
if(pos && x[pos] > 1 && val == 1) poss.erase(pos);
if(pos && x[pos] == 1 && val > 1) poss.insert(pos);
xmult = (xmult * Inv(x[pos])) % mod;
xmult = (xmult * (x[pos] = val)) % mod;
return solve();
}
int updateY(int pos , int val){
upd(pos , y[pos] = val);
return solve();
}
///int main (){}