| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 925288 | Karoot | 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 "horses.h"
#include <iostream>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
typedef long long ll;
ll linf = 1e15+1;
inline void scoobydoobydoo(){
ios::sync_with_stdio(false);
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
}
typedef unsigned long long ull;
ull modmul(ull a, ull b, ull M) {
ll ret = a * b - M * ull(1.L / M * a * b);
return ret + M * (ret < 0) - M * (ret >= (ll)M);
}
ull modpow(ull b, ull e, ull mod) {
ull ans = 1;
for (; e; b = modmul(b, b, mod), e /= 2)
if (e & 1) ans = modmul(ans, b, mod);
return ans;
}
const int M = 1e9+7;
const int MAXN = 5e5+1;
long double X[MAXN], Y[MAXN];
struct Node {
long double sum;
long double maxi;
ll multi;
ll index;
};
Node ST[4*MAXN];
int leftOf[4*MAXN], rightOf[4*MAXN];
int indexToNode[MAXN];
void buildTree(int l, int r, int node = 1){
leftOf[node] = l; rightOf[node] = r;
if (l == r){
indexToNode[l] = node;
ST[node].index = l;
ST[node].maxi = log10(Y[l]);
ST[node].sum = log10(X[l]);
ST[node].maxi += ST[node].sum;
ST[node].multi = X[l];
return;
}
int mid = (l+r)>>1;
buildTree(l, mid, 2*node);
buildTree(mid+1, r, 2*node+1);
ST[node].sum = ST[2*node].sum + ST[2*node+1].sum;
if (ST[2*node].maxi > ST[2*node+1].maxi+ST[2*node].sum){
ST[node].index = ST[2*node].index;
ST[node].maxi = ST[2*node].maxi;
} else {
ST[node].index = ST[2*node+1].index;
ST[node].maxi = ST[2*node+1].maxi+ST[2*node].sum;
}
ST[node].multi = modmul(ST[2*node].multi, ST[2*node+1].multi, M);
return;
}
ll multQuery(int l, int r, int node = 1){
if (leftOf[node] == l && rightOf[node] == r){
return ST[node].multi;
}
int a = node*2, b = node*2+1;
if (r <= rightOf[a])return multQuery(l, r, a);
return modmul(multQuery(l, rightOf[a], a), multQuery(leftOf[b], r, b), M);
}
int query(){
ll index = ST[1].index;
ll ans = modmul(Y[index], multQuery(0, index), M);
return ans;
}
void update1(int node){
if (!node)return;
ST[node].sum = ST[2*node].sum + ST[2*node+1].sum;
if (ST[2*node].maxi > ST[2*node+1].maxi+ST[2*node].sum){
ST[node].index = ST[2*node].index;
ST[node].maxi = ST[2*node].maxi;
} else {
ST[node].index = ST[2*node+1].index;
ST[node].maxi = ST[2*node+1].maxi+ST[2*node].sum;
}
update1(node>>1);
}
int updateX(int pos, int val){
ST[indexToNode[pos]].sum = log10((long double)val);
ST[indexToNode[pos]].maxi = log10((long double)val) + log10(Y[pos]);
update1(indexToNode[pos]>>1);
X[pos] = val;
return query();
}
int updateY(int pos, int val){
ST[indexToNode[pos]].maxi = log10((long double)val) + log10(X[pos]);
update1(indexToNode[pos]>>1);
Y[pos] = val;
return query();
}
int init(int n, int x[], int y[]) {
for(int i = 0; i < n; i++){
X[i] = x[i];
Y[i] = y[i];
}
buildTree(0, n-1);
return query();
}
int main(){
scoobydoobydoo();
cout << fixed << setprecision(8);
int x[4] = {5, 3, 2, 2};
int y[4] = {9, 8, 3, 1};
cout << init(4, x, y) << endl;
return 0;
}