| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 395785 | peuch | 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<bits/stdc++.h>
using namespace std;
const long long MAXN = 5e5 + 10;
const long long MOD = 1e9 + 7;
long long n;
long long x[MAXN], y[MAXN];
long long segX[4 * MAXN], segY[4 * MAXN], segV[4 * MAXN];
long long merge(long long pos, long long e, long long d);
void buildY(long long pos, long long ini, long long fim);
void buildX(long long pos, long long ini, long long fim);
void buildV(long long pos, long long ini, long long fim);
long long queryX(long long pos, long long ini, long long fim, long long p, long long q);
long long queryV(long long pos, long long ini, long long fim, long long p, long long q);
void upY(long long pos, long long ini, long long fim, long long id);
void upX(long long pos, long long ini, long long fim, long long id);
void upV(long long pos, long long ini, long long fim, long long id);
long long init(long long N, long long X[], long long Y[]) {
n = N;
for(long long i = 1; i <= n; i++)
x[i] = X[i - 1], y[i] = Y[i - 1];
buildX(1, 1, n);
buildV(1, 1, n);
buildY(1, 1, n);
return (y[segY[1]] * queryV(1, 1, n, 1, segY[1])) % MOD;
}
long long merge(long long e, long long d){
long long aux = queryX(1, 1, n, e + 1, d);
if(aux * y[d] >= y[e]) return d;
else return e;
}
void buildY(long long pos, long long ini, long long fim){
if(ini == fim){
segY[pos] = ini;
return;
}
long long mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
buildY(e, ini, mid);
buildY(d, mid + 1, fim);
segY[pos] = merge(segY[e], segY[d]);
}
void buildX(long long pos, long long ini, long long fim){
if(ini == fim){
segX[pos] = x[ini];
return;
}
long long mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
buildX(e, ini, mid);
buildX(d, mid + 1, fim);
segX[pos] = min(MOD, segX[e] * segX[d]);
}
void buildV(long long pos, long long ini, long long fim){
if(ini == fim){
segV[pos] = x[ini];
return;
}
long long mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
buildV(e, ini, mid);
buildV(d, mid + 1, fim);
segV[pos] = (segV[e] * segV[d]) % MOD;
}
long long queryX(long long pos, long long ini, long long fim, long long p, long long q){
if(ini > q || fim < p) return 1;
if(ini >= p && fim <= q) return segX[pos];
long long mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
return min(queryX(e, ini, mid, p, q) * queryX(d, mid + 1, fim, p, q), MOD);
}
long long queryV(long long pos, long long ini, long long fim, long long p, long long q){
if(ini > q || fim < p) return 1;
if(ini >= p && fim <= q) return segV[pos];
long long mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
return (queryV(e, ini, mid, p, q) * queryV(d, mid + 1, fim, p, q)) % MOD;
}
void upY(long long pos, long long ini, long long fim, long long id){
if(ini > id || fim < id) return;
if(ini == fim) return;
long long mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
upY(e, ini, mid, id);
upY(d, mid + 1, fim, id);
segY[pos] = merge(segY[e], segY[d]);
}
void upX(long long pos, long long ini, long long fim, long long id){
if(ini > id || fim < id) return;
if(ini == fim) {segX[pos] = x[id]; return;}
long long mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
upX(e, ini, mid, id);
upX(d, mid + 1, fim, id);
segX[pos] = min(MOD, segX[e] * segX[d]);
}
void upV(long long pos, long long ini, long long fim, long long id){
if(ini > id || fim < id) return;
if(ini == fim) {segV[pos] = x[id]; return;}
long long mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
upV(e, ini, mid, id);
upV(d, mid + 1, fim, id);
segV[pos] = (segV[e] * segV[d]) % MOD;
}
long long updateY(long long pos, long long val){
y[pos] = val;
upY(1, 1, n, pos);
return (y[segY[1]] * queryV(1, 1, n, 1, segY[1])) % MOD;
}
long long updateX(long long pos, long long val){
x[pos] = val;
upX(1, 1, n, pos);
upV(1, 1, n, pos);
return (y[segY[1]] * queryV(1, 1, n, 1, segY[1])) % MOD;
}