| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 330930 | monkey8 | 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 <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cstdio>
#include <utility>
#include <queue>
#include <math.h>
#include <set>
#include <bitset>
#include <cmath>
#include <bitset>
#include <iterator>
#include <limits>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, int> pdi;
const ll MOD = 1e9 + 7;
const int MAXN = 500010;
pdi st[MAXN << 2];
double lazy[MAXN << 2];
ll st1[MAXN << 2];
ll lazy1[MAXN << 2];
int xval[MAXN];
int yval[MAXN];
int left(int p) {
return (p << 1);
}
int right(int p) {
return (p << 1) + 1;
}
void build(int p, int L, int R) {
if(L == R) st[p] = pdi(0, L);
else {
build(left(p), L, (L + R)/2);
build(right(p), (L + R)/2 + 1, R);
st[p] = max(st[left(p)], st[right(p)]);
}
}
void push(int p, int L, int R) {
st[p].first += lazy[p];
if(L != R) {
lazy[left(p)] += lazy[p];
lazy[right(p)] += lazy[p];
}
lazy[p] = 0;
}
void update(int p, int L, int R, int i, int j, double val) {
push(p, L, R);
if(i > R || j < L) return;
if(L >= i && R <= j) {
lazy[p] += val;
push(p, L, R);
return;
}
update(left(p), L, (L + R)/2, i, j, val);
update(right(p), (L + R)/2 + 1, R, i, j, val);
st[p] = max(st[left(p)], st[right(p)]);
}
pdi query(int p, int L, int R, int i, int j) {
push(p, L, R);
if(i > R || j < L) return pdi(-1, -1);
if(L >= i && R <= j) return st[p];
return max(query(left(p), L, (L + R)/2, i, j), query(right(p), (L + R)/2 + 1, R, i, j));
}
void build1(int p, int L, int R) {
st1[p] = 1;
lazy1[p] = 1;
if(L == R) return;
build1(left(p), L, (L + R)/2);
build1(right(p), (L + R)/2 + 1, R);
}
void push1(int p, int L, int R) {
st1[p] = (st1[p] * lazy1[p]) % MOD;
if(L != R) {
lazy1[left(p)] = (lazy1[left(p)] * lazy1[p]) % MOD;
lazy1[right(p)] = (lazy1[right(p)] * lazy1[p]) % MOD;
}
lazy1[p] = 1;
}
void update1(int p, int L, int R, int i, int j, ll val) {
push1(p, L, R);
if(i > R || j < L) return;
if(L >= i && R <= j) {
lazy1[p] = (lazy1[p] * val) % MOD;
push1(p, L, R);
return;
}
update1(left(p), L, (L + R)/2, i, j, val);
update1(right(p), (L + R)/2 + 1, R, i, j, val);
st1[p] = max(st1[left(p)], st1[right(p)]);
}
ll query1(int p, int L, int R, int i) {
push1(p, L, R);
if(L == R && i == L) return st1[p];
if(i < L || i > R) return 0;
return max(query1(left(p), L, (L + R)/2, i), query1(right(p), (L + R)/2 + 1, R, i));
}
ll poww(ll x, ll y) {
if(y == 0) return 1;
ll z = poww(x, y/2);
if(y % 2 == 0) return (z * z) % MOD;
return (((z * z) % MOD) * x) % MOD;
}
int N;
int init(int n, vector<int> x, vector<int> y) {
N = n;
build(1, 0, n - 1);
build1(1, 0, n - 1);
for(int i = 0; i < n; i++) {
xval[i] = x[i];
update(1, 0, n - 1, i, n - 1, log2(x[i]));
update1(1, 0, n - 1, i, n - 1, x[i]);
}
for(int i = 0; i < n; i++) {
yval[i] = y[i];
update(1, 0, n - 1, i, i, log2(y[i]));
update1(1, 0, n - 1, i, i, y[i]);
}
pdi q = query(1, 0, n - 1, 0, n - 1);
return query1(1, 0, n - 1, q.second);
}
int updateX(int pos, int val) {
update(1, 0, N - 1, pos, N - 1, log2(val) - log2(xval[pos]));
update1(1, 0, N - 1, pos, N - 1, ((ll)val * poww(xval[pos], MOD - 2)) % MOD);
xval[pos] = val;
pdi q = query(1, 0, N - 1, 0, N - 1);
return query1(1, 0, N - 1, q.second);
}
int updateY(int pos, int val) {
update(1, 0, N - 1, pos, pos, log2(val) - log2(yval[pos]));
update1(1, 0, N - 1, pos, pos, ((ll)val * poww(yval[pos], MOD - 2)) % MOD);
yval[pos] = val;
pdi q = query(1, 0, N - 1, 0, N - 1);
return query1(1, 0, N - 1, q.second);
}