| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 160297 | FiloSanza | 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;
inline int left(int i){return i*2+1;}
inline int right(int i){return (i+1)*2;}
const int MOD = 1e9+7;
int S;
vector<pair<int, bool>> segX;
vector<int> segM;
vector<int> Y;
pair<int, bool> mergeX(pair<int, bool> a, pair<int, bool> b){
long long prod = 1LL * a.first * a.second;
bool overflow = a.second || b.second || prod >= MOD;
return {prod % MOD, overflow};
}
pair<int, bool> QueryX(int pos, int l, int r, int a, int b){
if(l > b || r < a) return {1, false};
if(l >= a && r <= b) return segX[pos];
int mid = (l+r)/2;
return mergeX(
QueryX(left(pos), l, mid, a, b),
QueryX(right(pos), mid+1, r, a, b)
);
}
int mergeY(int a, int b){
auto q = QueryX(0, a+1, b+1, 0, S/2);
if(q.second) return b;
return Y[a] > 1LL * Y[b] * q.first ? a : b;
}
int init(int N, int X[], int _Y[]) {
S = (1 << (int)ceil(log2(N)+1)) - 1;
segX.resize(S, 1);
segM.resize(S);
Y.resize(N);
for(int i=0; i<N; i++){
segX[i+S/2] = {X[i], false};
segM[i+S/2] = i;
Y[i] = _Y[i];
}
for(int i=S/2-1; i>=0; i--){
segX[i] = mergeX(segX[left(i)], segX[right(i)]);
segM[i] = mergeY(segM[left(i)], segM[right(i)]);
}
for(auto i : segX) cout << i.first << " ";
cout << "\n";
return 1LL * QueryX(0, 0, S/2, 0, N-1).first * Y[segM[0]] % MOD;
}
int updateX(int pos, int val) {
return 0;
}
int updateY(int pos, int val) {
return 0;
}