#include "horses.h"
#include <bits/stdc++.h>
#define long long long
using namespace std;
const int N = 1<<19, M = 1e9+7;
int n, X[N], Y[N];
double t[N<<1], lz[N<<1];
long val[N<<1], lzval[N<<1];
long powMod(long a, long b) {
long ret = 1;
while(b) {
if(b & 1) ret = (ret * a) % M;
a = (a * a) % M;
b >>= 1;
}
return ret;
}
int invMod(long v) {
return (int)powMod(v, M-2);
}
void update(int p) {
if(t[p<<1] > t[p<<1|1]) val[p] = val[p<<1], t[p] = t[p<<1];
else val[p] = val[p<<1|1], t[p] = t[p<<1|1];
}
void push(int p, int l, int r) {
if(lzval[p] != 1 || lz[p] != 0.0) {
val[p] = (val[p] * lzval[p]) % M;
t[p] += lz[p];
if(l != r) {
lzval[p<<1] = (lzval[p<<1] * lzval[p]) % M;
lzval[p<<1|1] = (lzval[p<<1|1] * lzval[p]) % M;
lz[p<<1] += lz[p];
lz[p<<1|1] += lz[p];
}
}
lzval[p] = 1, lz[p] = 0.0;
}
void build(int p = 1, int l = 0, int r = n-1) {
if(l == r) {
t[p] = log2(Y[l]);
val[p] = Y[l];
return;
}
int m = (l + r) >> 1;
build(p<<1, l, m), build(p<<1|1, m+1, r);
update(p);
}
template<typename T>
void travel(int x, int y, const T &f, int p = 1, int l = 0, int r = n-1) {
push(p, l, r);
if(x > r || l > y) return;
if(x <= l && r <= y) return f(p, l, r);
int m = (l + r) >> 1;
travel(x, y, f, p<<1, l, m), travel(x, y, f, p<<1|1, m+1, r);
update(p);
}
void modify(int x, int y, int a, double b) {
travel(x, y, [&](int p, int l, int r) {
lz[p] += b;
lzval[p] = (lzval[p] * a) % M;
push(p, l, r);
});
}
int init(int z, int x[], int y[]) {
n = z;
for(int i = 0; i < n; ++i) X[i] = x[i], Y[i] = y[i];
fill(lzval, lzval + (::N<<1), 1);
build();
for(int i = 0; i < n; ++i) modify(i, n-1, X[i], log2(X[i]));
return (int)val[1];
}
int updateX(int pos, int v) {
modify(pos, n-1, invMod(X[pos]), -log2(X[pos]));
modify(pos, n-1, v, log2(v));
X[pos] = v;
return (int)val[1];
}
int updateY(int pos, int v) {
modify(pos, pos, invMod(Y[pos]), -log2(Y[pos]));
modify(pos, pos, v, log2(v));
Y[pos] = v;
return (int)val[1];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
8568 KB |
Output is correct |
2 |
Correct |
8 ms |
8568 KB |
Output is correct |
3 |
Correct |
9 ms |
8632 KB |
Output is correct |
4 |
Correct |
9 ms |
8764 KB |
Output is correct |
5 |
Correct |
8 ms |
8764 KB |
Output is correct |
6 |
Correct |
8 ms |
8764 KB |
Output is correct |
7 |
Correct |
8 ms |
8792 KB |
Output is correct |
8 |
Correct |
8 ms |
8796 KB |
Output is correct |
9 |
Correct |
8 ms |
8804 KB |
Output is correct |
10 |
Correct |
8 ms |
8848 KB |
Output is correct |
11 |
Correct |
8 ms |
8868 KB |
Output is correct |
12 |
Correct |
7 ms |
8872 KB |
Output is correct |
13 |
Correct |
8 ms |
8876 KB |
Output is correct |
14 |
Correct |
7 ms |
8880 KB |
Output is correct |
15 |
Correct |
8 ms |
8888 KB |
Output is correct |
16 |
Correct |
8 ms |
8888 KB |
Output is correct |
17 |
Correct |
9 ms |
8896 KB |
Output is correct |
18 |
Correct |
8 ms |
8900 KB |
Output is correct |
19 |
Correct |
8 ms |
8904 KB |
Output is correct |
20 |
Correct |
8 ms |
8908 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
8912 KB |
Output is correct |
2 |
Correct |
8 ms |
8916 KB |
Output is correct |
3 |
Correct |
7 ms |
8996 KB |
Output is correct |
4 |
Correct |
8 ms |
9000 KB |
Output is correct |
5 |
Correct |
8 ms |
9004 KB |
Output is correct |
6 |
Correct |
7 ms |
9008 KB |
Output is correct |
7 |
Correct |
8 ms |
9012 KB |
Output is correct |
8 |
Correct |
8 ms |
9016 KB |
Output is correct |
9 |
Correct |
8 ms |
9020 KB |
Output is correct |
10 |
Correct |
8 ms |
9028 KB |
Output is correct |
11 |
Correct |
8 ms |
9028 KB |
Output is correct |
12 |
Correct |
8 ms |
9028 KB |
Output is correct |
13 |
Correct |
7 ms |
9040 KB |
Output is correct |
14 |
Correct |
8 ms |
9040 KB |
Output is correct |
15 |
Correct |
7 ms |
9120 KB |
Output is correct |
16 |
Correct |
7 ms |
9120 KB |
Output is correct |
17 |
Correct |
7 ms |
9120 KB |
Output is correct |
18 |
Correct |
8 ms |
9120 KB |
Output is correct |
19 |
Correct |
7 ms |
9120 KB |
Output is correct |
20 |
Correct |
8 ms |
9120 KB |
Output is correct |
21 |
Correct |
8 ms |
9120 KB |
Output is correct |
22 |
Correct |
8 ms |
9120 KB |
Output is correct |
23 |
Correct |
9 ms |
9160 KB |
Output is correct |
24 |
Correct |
9 ms |
9196 KB |
Output is correct |
25 |
Correct |
9 ms |
9232 KB |
Output is correct |
26 |
Correct |
10 ms |
9300 KB |
Output is correct |
27 |
Correct |
8 ms |
9324 KB |
Output is correct |
28 |
Correct |
9 ms |
9340 KB |
Output is correct |
29 |
Correct |
9 ms |
9340 KB |
Output is correct |
30 |
Correct |
10 ms |
9368 KB |
Output is correct |
31 |
Correct |
10 ms |
9420 KB |
Output is correct |
32 |
Correct |
9 ms |
9468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
474 ms |
42944 KB |
Output is correct |
2 |
Correct |
634 ms |
55528 KB |
Output is correct |
3 |
Correct |
591 ms |
59328 KB |
Output is correct |
4 |
Correct |
638 ms |
66948 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
66948 KB |
Output is correct |
2 |
Correct |
9 ms |
66948 KB |
Output is correct |
3 |
Correct |
8 ms |
66948 KB |
Output is correct |
4 |
Correct |
9 ms |
66948 KB |
Output is correct |
5 |
Correct |
7 ms |
66948 KB |
Output is correct |
6 |
Correct |
8 ms |
66948 KB |
Output is correct |
7 |
Correct |
7 ms |
66948 KB |
Output is correct |
8 |
Correct |
8 ms |
66948 KB |
Output is correct |
9 |
Correct |
8 ms |
66948 KB |
Output is correct |
10 |
Correct |
10 ms |
66948 KB |
Output is correct |
11 |
Correct |
9 ms |
66948 KB |
Output is correct |
12 |
Correct |
8 ms |
66948 KB |
Output is correct |
13 |
Correct |
8 ms |
66948 KB |
Output is correct |
14 |
Correct |
8 ms |
66948 KB |
Output is correct |
15 |
Correct |
8 ms |
66948 KB |
Output is correct |
16 |
Correct |
10 ms |
66948 KB |
Output is correct |
17 |
Correct |
8 ms |
66948 KB |
Output is correct |
18 |
Correct |
7 ms |
66948 KB |
Output is correct |
19 |
Correct |
10 ms |
66948 KB |
Output is correct |
20 |
Correct |
7 ms |
66948 KB |
Output is correct |
21 |
Correct |
8 ms |
66948 KB |
Output is correct |
22 |
Correct |
8 ms |
66948 KB |
Output is correct |
23 |
Correct |
10 ms |
66948 KB |
Output is correct |
24 |
Correct |
9 ms |
66948 KB |
Output is correct |
25 |
Correct |
9 ms |
66948 KB |
Output is correct |
26 |
Correct |
11 ms |
66948 KB |
Output is correct |
27 |
Correct |
12 ms |
66948 KB |
Output is correct |
28 |
Correct |
11 ms |
66948 KB |
Output is correct |
29 |
Correct |
9 ms |
66948 KB |
Output is correct |
30 |
Correct |
9 ms |
66948 KB |
Output is correct |
31 |
Correct |
12 ms |
66948 KB |
Output is correct |
32 |
Correct |
10 ms |
66948 KB |
Output is correct |
33 |
Correct |
361 ms |
70332 KB |
Output is correct |
34 |
Correct |
340 ms |
74256 KB |
Output is correct |
35 |
Correct |
395 ms |
85080 KB |
Output is correct |
36 |
Correct |
417 ms |
96004 KB |
Output is correct |
37 |
Correct |
289 ms |
98088 KB |
Output is correct |
38 |
Correct |
342 ms |
101048 KB |
Output is correct |
39 |
Correct |
297 ms |
102920 KB |
Output is correct |
40 |
Correct |
356 ms |
109032 KB |
Output is correct |
41 |
Correct |
348 ms |
111024 KB |
Output is correct |
42 |
Correct |
279 ms |
113144 KB |
Output is correct |
43 |
Correct |
348 ms |
119356 KB |
Output is correct |
44 |
Correct |
345 ms |
125776 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
125776 KB |
Output is correct |
2 |
Correct |
7 ms |
125776 KB |
Output is correct |
3 |
Correct |
8 ms |
125776 KB |
Output is correct |
4 |
Correct |
8 ms |
125776 KB |
Output is correct |
5 |
Correct |
7 ms |
125776 KB |
Output is correct |
6 |
Correct |
8 ms |
125776 KB |
Output is correct |
7 |
Correct |
7 ms |
125776 KB |
Output is correct |
8 |
Correct |
8 ms |
125776 KB |
Output is correct |
9 |
Correct |
7 ms |
125776 KB |
Output is correct |
10 |
Correct |
7 ms |
125776 KB |
Output is correct |
11 |
Correct |
7 ms |
125776 KB |
Output is correct |
12 |
Correct |
7 ms |
125776 KB |
Output is correct |
13 |
Correct |
8 ms |
125776 KB |
Output is correct |
14 |
Correct |
8 ms |
125776 KB |
Output is correct |
15 |
Correct |
8 ms |
125776 KB |
Output is correct |
16 |
Correct |
8 ms |
125776 KB |
Output is correct |
17 |
Correct |
8 ms |
125776 KB |
Output is correct |
18 |
Correct |
8 ms |
125776 KB |
Output is correct |
19 |
Correct |
8 ms |
125776 KB |
Output is correct |
20 |
Correct |
8 ms |
125776 KB |
Output is correct |
21 |
Correct |
7 ms |
125776 KB |
Output is correct |
22 |
Correct |
8 ms |
125776 KB |
Output is correct |
23 |
Correct |
10 ms |
125776 KB |
Output is correct |
24 |
Correct |
9 ms |
125776 KB |
Output is correct |
25 |
Correct |
9 ms |
125776 KB |
Output is correct |
26 |
Correct |
9 ms |
125776 KB |
Output is correct |
27 |
Correct |
9 ms |
125776 KB |
Output is correct |
28 |
Correct |
11 ms |
125776 KB |
Output is correct |
29 |
Correct |
9 ms |
125776 KB |
Output is correct |
30 |
Correct |
9 ms |
125776 KB |
Output is correct |
31 |
Correct |
9 ms |
125776 KB |
Output is correct |
32 |
Correct |
9 ms |
125776 KB |
Output is correct |
33 |
Correct |
463 ms |
130804 KB |
Output is correct |
34 |
Correct |
646 ms |
143504 KB |
Output is correct |
35 |
Correct |
585 ms |
147248 KB |
Output is correct |
36 |
Correct |
632 ms |
154816 KB |
Output is correct |
37 |
Correct |
360 ms |
157856 KB |
Output is correct |
38 |
Correct |
340 ms |
161932 KB |
Output is correct |
39 |
Correct |
382 ms |
172800 KB |
Output is correct |
40 |
Correct |
445 ms |
183520 KB |
Output is correct |
41 |
Correct |
299 ms |
185732 KB |
Output is correct |
42 |
Correct |
524 ms |
188684 KB |
Output is correct |
43 |
Correct |
329 ms |
190560 KB |
Output is correct |
44 |
Correct |
370 ms |
196604 KB |
Output is correct |
45 |
Correct |
287 ms |
198700 KB |
Output is correct |
46 |
Correct |
284 ms |
200808 KB |
Output is correct |
47 |
Correct |
360 ms |
207096 KB |
Output is correct |
48 |
Correct |
378 ms |
213412 KB |
Output is correct |
49 |
Correct |
601 ms |
219460 KB |
Output is correct |
50 |
Correct |
627 ms |
224444 KB |
Output is correct |
51 |
Correct |
552 ms |
236400 KB |
Output is correct |
52 |
Correct |
572 ms |
247628 KB |
Output is correct |
53 |
Correct |
507 ms |
251060 KB |
Output is correct |
54 |
Correct |
503 ms |
255020 KB |
Output is correct |
55 |
Correct |
396 ms |
257408 KB |
Output is correct |
56 |
Correct |
541 ms |
264816 KB |
Output is correct |
57 |
Correct |
423 ms |
267684 KB |
Output is correct |
58 |
Correct |
412 ms |
270904 KB |
Output is correct |
59 |
Correct |
354 ms |
276332 KB |
Output is correct |