#include "horses.h"
#include<bits/stdc++.h>
#define int long long int
using namespace std;
int x[500005], y[500005], segp[4*500005], segm[4*500005], mod = 1e9+7;
void buildp(int n, int l, int r) {
if (l == r) {
segp[n] = x[l];
} else {
int m = (l+r)/2;
buildp(2*n, l, m);
buildp(2*n+1, m+1, r);
segp[n] = segp[2*n] * segp[2*n+1];
segp[n] %= mod;
}
}
void buildm(int n, int l, int r) {
if (l == r) {
segm[n] = y[l];
} else {
int m = (l+r)/2;
buildm(2*n, l, m);
buildm(2*n+1, m+1, r);
segm[n] = max(segm[2*n], segm[2*n+1]);
}
}
void updatep(int n, int l, int r, int i, int v) {
if (l == r) {
segp[n] = v;
} else {
int m = (l+r)/2;
if (l <= i && i <= m) {
updatep(2*n, l, m, i, v);
} else {
updatep(2*n+1, m+1, r, i, v);
}
segp[n] = segp[2*n] * segp[2*n+1];
segp[n] %= mod;
}
}
void updatem(int n, int l, int r, int i, int v) {
if (l == r) {
segm[n] = v;
} else {
int m = (l+r)/2;
if (l <= i && i <= m) {
updatem(2*n, l, m, i, v);
} else {
updatem(2*n+1, m+1, r, i, v);
}
segm[n] = max(segm[2*n], segm[2*n+1]);
}
}
int queryp(int n, int l, int r, int a, int b) {
if (b < l || r < a) {
return 1;
} else if (a <= l && r <= b) {
return segp[n];
} else {
int m = (l+r)/2;
return (queryp(2*n, l, m, a, b)*queryp(2*n+1, m+1, r, a, b))%mod;
}
}
int querym(int n, int l, int r, int a, int b) {
if (b < l || r < a) {
return 0;
} else if (a <= l && r <= b) {
return segm[n];
} else {
int m = (l+r)/2;
return max(querym(2*n, l, m, a, b), querym(2*n+1, m+1, r, a, b));
}
}
int n;
set<pair<int, int>> segs;
int32_t calc() {
int ind = 0, co = 0;
auto j = segs.end();
while(j != segs.begin()) {
if (co > 63) {
break;
}
co++;
j--;
}
long double v = 0, a = 0, b = 0;
for (; j != segs.end(); j++) {
auto [l, r] = *j;
if (l == r) {
a += log2(x[l]);
if (a+log2(y[l]) > v) {
v = a+log2(y[l]);
ind = l;
}
} else {
int mx = querym(1, 0, n-1, l, r);
if (a+log2(mx) > v) {
v = a+log2(mx);
ind = l;
}
}
}
return (queryp(1, 0, n-1, 0, ind)*y[ind]) % mod;
}
int32_t init(int32_t N, int32_t X[], int32_t Y[]) {
n = N;
int l = -1, r = 0;
for (int i = 0; i < n; i++) {
x[i] = X[i];
y[i] = Y[i];
if (x[i] == 1) {
if (l == -1) {
l = i;
}
r = i;
} else {
if (l != -1) {
segs.insert({l, r});
}
l = -1;
segs.insert({i, i});
}
}
if (l != -1) {
segs.insert({l, r});
}
buildp(1, 0, n-1);
buildm(1, 0, n-1);
return calc();
}
int32_t updateX(int32_t pos, int32_t val) {
if (x[pos] == 1 && val != 1) {
auto i = segs.upper_bound({pos, pos});
i--;
auto [l, r] = *i;
segs.erase(i);
if (l != pos) {
segs.insert({l, pos-1});
}
segs.insert({pos, pos});
if (r != pos) {
segs.insert({pos+1, r});
}
} else if (x[pos] != 1 && val == 1) {
auto i = segs.lower_bound({pos, pos});
set<pair<int, int>> todel;
todel.insert({pos, pos});
int ll = pos, rr = pos;
if (pos != 0 && x[pos-1] == 1) {
i--;
auto [l, r] = *i;
ll = l;
todel.insert({l, r});
i++;
}
if (pos != n-1 && x[pos+1] == 1) {
i++;
auto [l, r] = *i;
rr = r;
todel.insert({l, r});
}
for (auto c : todel) {
segs.erase(c);
}
segs.insert({ll, rr});
}
x[pos] = val;
updatep(1, 0, n-1, pos, val);
return calc();
}
int32_t updateY(int32_t pos, int32_t val) {
y[pos] = val;
updatem(1, 0, n-1, pos, val);
return calc();
}
Compilation message
horses.cpp: In function 'int32_t calc()':
horses.cpp:104:47: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
104 | return (queryp(1, 0, n-1, 0, ind)*y[ind]) % mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:86:31: warning: unused variable 'b' [-Wunused-variable]
86 | long double v = 0, a = 0, b = 0;
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
272 ms |
63404 KB |
Output is correct |
| 2 |
Correct |
348 ms |
63316 KB |
Output is correct |
| 3 |
Correct |
266 ms |
63312 KB |
Output is correct |
| 4 |
Correct |
324 ms |
63316 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8576 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
