#include "horses.h"
#include<cmath>
#include<algorithm>
#include <cassert>
#include <cstdio>
using namespace std;
using pdi = pair<double, int>;
#define ff first
#define ss second
constexpr int maxn = 5e5+10, mod = 1000000007;
int *x, *y, n, val_pref[maxn];
double pref[maxn];
int power(int b, int e) {
int ans = 1;
while(e) {
if(e&1) ans = (int)(1ll * ans * b % mod);
b = (int)(1ll * b * b % mod);
e >>= 1;
}
return ans;
}
struct SegmentTree
{
pdi tree[4*maxn], lazy[4*maxn];
void build(int node, int i, int j) {
lazy[node] = {0, 1};
if(i == j) {
tree[node] = {pref[i] + log2(y[i]), (int)(1ll * val_pref[i] * y[i] % mod)};
return;
}
int m = (i+j) >> 1;
build(2*node, i, m); build(2*node+1, m+1, j);
tree[node] = max(tree[2*node], tree[2*node+1]);
}
void flush(int node, int i, int j) {
if(!lazy[node].ff) return;
if(i != j) {
lazy[2*node].ff += lazy[node].ff;
lazy[2*node+1].ff += lazy[node].ff;
lazy[2*node].ss = (int)(1ll * lazy[node].ss * lazy[2*node].ss % mod);
lazy[2*node+1].ss = (int)(1ll * lazy[node].ss * lazy[2*node+1].ss % mod);
}
tree[node].ff += lazy[node].ff;
tree[node].ss = (int)(1ll * tree[node].ss * lazy[node].ss % mod);
lazy[node] = {0, 1};
}
void upd(int node, int i, int j, int l, int r, pdi val) {
flush(node, i, j);
if(i > r || j < l) return;
if(i >= l && j <= r) {
lazy[node] = val;
flush(node, i, j);
return;
}
int m = (i+j) >> 1;
upd(2*node, i, m, l, r, val);
upd(2*node+1, m+1, j, l, r, val);
tree[node] = max(tree[2*node], tree[2*node+1]);
}
pdi query() {
flush(1, 0, n-1);
return tree[1];
}
} seg;
int init(int N, int X[], int Y[]) {
x = X; y = Y; n = N;
for(int i = 0; i < n; i++) {
pref[i] = (i?pref[i-1]:0) + log2(x[i]);
val_pref[i] = (int)(1ll * (i?val_pref[i-1]:1) * x[i] % mod);
}
seg.build(1, 0, n-1);
return seg.query().ss;
}
int updateX(int pos, int val) {
int mudar = (int)(1ll * val * power(x[pos], mod-2) % mod);
pdi v = {log2(val) - log2(x[pos]), mudar};
seg.upd(1, 0, n-1, pos, n-1, v);
x[pos] = val;
return seg.query().ss;
}
int updateY(int pos, int val) {
int mudar = (int)(1ll * val * power(y[pos], mod-2) % mod);
pdi v = {log2(val) - log2(y[pos]), mudar};
y[pos] = val;
seg.upd(1, 0, n-1, pos, pos, v);
return seg.query().ss;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
0 ms |
364 KB |
Output is correct |
4 |
Correct |
0 ms |
364 KB |
Output is correct |
5 |
Correct |
0 ms |
364 KB |
Output is correct |
6 |
Correct |
0 ms |
364 KB |
Output is correct |
7 |
Correct |
0 ms |
364 KB |
Output is correct |
8 |
Correct |
0 ms |
364 KB |
Output is correct |
9 |
Correct |
0 ms |
364 KB |
Output is correct |
10 |
Correct |
0 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
0 ms |
364 KB |
Output is correct |
13 |
Correct |
0 ms |
364 KB |
Output is correct |
14 |
Correct |
0 ms |
364 KB |
Output is correct |
15 |
Correct |
0 ms |
364 KB |
Output is correct |
16 |
Correct |
0 ms |
364 KB |
Output is correct |
17 |
Correct |
0 ms |
364 KB |
Output is correct |
18 |
Correct |
0 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
0 ms |
364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
0 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
0 ms |
364 KB |
Output is correct |
6 |
Correct |
0 ms |
364 KB |
Output is correct |
7 |
Correct |
0 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
0 ms |
364 KB |
Output is correct |
10 |
Correct |
0 ms |
364 KB |
Output is correct |
11 |
Correct |
0 ms |
364 KB |
Output is correct |
12 |
Correct |
0 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
0 ms |
364 KB |
Output is correct |
16 |
Correct |
0 ms |
364 KB |
Output is correct |
17 |
Correct |
0 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
0 ms |
364 KB |
Output is correct |
21 |
Correct |
0 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
492 KB |
Output is correct |
24 |
Correct |
2 ms |
492 KB |
Output is correct |
25 |
Correct |
1 ms |
492 KB |
Output is correct |
26 |
Correct |
1 ms |
492 KB |
Output is correct |
27 |
Correct |
1 ms |
492 KB |
Output is correct |
28 |
Correct |
1 ms |
492 KB |
Output is correct |
29 |
Correct |
1 ms |
364 KB |
Output is correct |
30 |
Correct |
2 ms |
620 KB |
Output is correct |
31 |
Correct |
1 ms |
492 KB |
Output is correct |
32 |
Correct |
1 ms |
492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
116 ms |
43952 KB |
Output is correct |
2 |
Correct |
290 ms |
43884 KB |
Output is correct |
3 |
Correct |
256 ms |
43884 KB |
Output is correct |
4 |
Correct |
269 ms |
44012 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
0 ms |
364 KB |
Output is correct |
4 |
Correct |
0 ms |
364 KB |
Output is correct |
5 |
Correct |
0 ms |
364 KB |
Output is correct |
6 |
Correct |
0 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
0 ms |
364 KB |
Output is correct |
10 |
Correct |
0 ms |
364 KB |
Output is correct |
11 |
Correct |
0 ms |
364 KB |
Output is correct |
12 |
Correct |
0 ms |
364 KB |
Output is correct |
13 |
Correct |
0 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
0 ms |
364 KB |
Output is correct |
16 |
Correct |
0 ms |
364 KB |
Output is correct |
17 |
Correct |
0 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
0 ms |
364 KB |
Output is correct |
20 |
Correct |
0 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
0 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
492 KB |
Output is correct |
24 |
Correct |
1 ms |
492 KB |
Output is correct |
25 |
Correct |
1 ms |
492 KB |
Output is correct |
26 |
Correct |
1 ms |
492 KB |
Output is correct |
27 |
Correct |
2 ms |
620 KB |
Output is correct |
28 |
Correct |
1 ms |
492 KB |
Output is correct |
29 |
Correct |
1 ms |
364 KB |
Output is correct |
30 |
Correct |
1 ms |
620 KB |
Output is correct |
31 |
Correct |
1 ms |
492 KB |
Output is correct |
32 |
Correct |
1 ms |
492 KB |
Output is correct |
33 |
Correct |
92 ms |
46936 KB |
Output is correct |
34 |
Correct |
89 ms |
46956 KB |
Output is correct |
35 |
Correct |
122 ms |
53996 KB |
Output is correct |
36 |
Correct |
111 ms |
53936 KB |
Output is correct |
37 |
Correct |
62 ms |
45164 KB |
Output is correct |
38 |
Correct |
78 ms |
46060 KB |
Output is correct |
39 |
Correct |
55 ms |
45036 KB |
Output is correct |
40 |
Correct |
90 ms |
49004 KB |
Output is correct |
41 |
Correct |
54 ms |
45036 KB |
Output is correct |
42 |
Correct |
53 ms |
45164 KB |
Output is correct |
43 |
Correct |
73 ms |
49388 KB |
Output is correct |
44 |
Correct |
72 ms |
49388 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
0 ms |
364 KB |
Output is correct |
5 |
Correct |
0 ms |
364 KB |
Output is correct |
6 |
Correct |
0 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
0 ms |
364 KB |
Output is correct |
9 |
Correct |
0 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
0 ms |
364 KB |
Output is correct |
13 |
Correct |
0 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
0 ms |
364 KB |
Output is correct |
16 |
Correct |
0 ms |
364 KB |
Output is correct |
17 |
Correct |
0 ms |
364 KB |
Output is correct |
18 |
Correct |
0 ms |
364 KB |
Output is correct |
19 |
Correct |
0 ms |
364 KB |
Output is correct |
20 |
Correct |
0 ms |
364 KB |
Output is correct |
21 |
Correct |
0 ms |
364 KB |
Output is correct |
22 |
Correct |
0 ms |
364 KB |
Output is correct |
23 |
Correct |
2 ms |
492 KB |
Output is correct |
24 |
Correct |
2 ms |
492 KB |
Output is correct |
25 |
Correct |
1 ms |
492 KB |
Output is correct |
26 |
Correct |
1 ms |
492 KB |
Output is correct |
27 |
Correct |
1 ms |
492 KB |
Output is correct |
28 |
Correct |
1 ms |
492 KB |
Output is correct |
29 |
Correct |
1 ms |
364 KB |
Output is correct |
30 |
Correct |
1 ms |
492 KB |
Output is correct |
31 |
Correct |
1 ms |
492 KB |
Output is correct |
32 |
Correct |
1 ms |
492 KB |
Output is correct |
33 |
Correct |
116 ms |
47724 KB |
Output is correct |
34 |
Correct |
296 ms |
56556 KB |
Output is correct |
35 |
Correct |
249 ms |
47780 KB |
Output is correct |
36 |
Correct |
273 ms |
51700 KB |
Output is correct |
37 |
Correct |
88 ms |
46956 KB |
Output is correct |
38 |
Correct |
91 ms |
47084 KB |
Output is correct |
39 |
Correct |
111 ms |
53996 KB |
Output is correct |
40 |
Correct |
109 ms |
53868 KB |
Output is correct |
41 |
Correct |
60 ms |
45164 KB |
Output is correct |
42 |
Correct |
76 ms |
46060 KB |
Output is correct |
43 |
Correct |
52 ms |
45036 KB |
Output is correct |
44 |
Correct |
80 ms |
49004 KB |
Output is correct |
45 |
Correct |
51 ms |
45036 KB |
Output is correct |
46 |
Correct |
51 ms |
45164 KB |
Output is correct |
47 |
Correct |
71 ms |
49388 KB |
Output is correct |
48 |
Correct |
73 ms |
49388 KB |
Output is correct |
49 |
Correct |
265 ms |
49164 KB |
Output is correct |
50 |
Correct |
269 ms |
49004 KB |
Output is correct |
51 |
Correct |
175 ms |
55788 KB |
Output is correct |
52 |
Correct |
171 ms |
55404 KB |
Output is correct |
53 |
Correct |
212 ms |
47340 KB |
Output is correct |
54 |
Correct |
151 ms |
47852 KB |
Output is correct |
55 |
Correct |
129 ms |
46188 KB |
Output is correct |
56 |
Correct |
178 ms |
50884 KB |
Output is correct |
57 |
Correct |
114 ms |
46700 KB |
Output is correct |
58 |
Correct |
117 ms |
47212 KB |
Output is correct |
59 |
Correct |
71 ms |
49388 KB |
Output is correct |