#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
#include "horses.h"
#define ld long double
#define i64 long long
using namespace std;
const i64 sz = 5e5 + 25;
const i64 md = 1e9 + 7;
i64 lz1m[sz * 4], lz1d[sz * 4];
i64 st1[sz * 4];
ld lz2m[sz * 4], lz2d[sz * 4];
pair<ld, i64> st2[sz * 4];
ld d[sz];
i64 a[sz], b[sz], c[sz];
i64 n;
i64 bp(i64 x, i64 b) {
i64 res = 1;
while (b) {
if (b & 1) res = (res * x) % md;
x = (x * x) % md;
b >>= 1;
}
return res;
}
void build1(i64 le, i64 ri, i64 v) {
lz1m[v] = 1;
lz1d[v] = 1;
if (le == ri) {
st1[v] = c[le] * b[le] % md;
return;
}
i64 mi = (le + ri) / 2;
build1(le, mi, v * 2);
build1(mi + 1, ri, v * 2 + 1);
st1[v] = (st1[v * 2] + st1[v * 2 + 1]) % md;
}
void relax1(i64 v, i64 le, i64 ri) {
if (lz1m[v] != 1 || lz1d[v] != 1) {
st1[v] = (st1[v] * lz1m[v]) % md;
st1[v] = (st1[v] * bp(lz1d[v], md - 2)) % md;
if (le != ri) {
lz1m[v * 2] = (lz1m[v * 2] * lz1m[v]) % md;
lz1m[v * 2 + 1] = (lz1m[v * 2 + 1] * lz1m[v]) % md;
lz1d[v * 2] = (lz1d[v * 2] * lz1d[v]) % md;
lz1d[v * 2 + 1] = (lz1d[v * 2 + 1] * lz1d[v]) % md;
}
lz1m[v] = 1;
lz1d[v] = 1;
}
}
void rupdate1(i64 le, i64 ri, i64 ql, i64 qr, i64 v, i64 m, i64 d) {
relax1(v, le, ri);
if (le > qr || ri < ql) return;
if (ql <= le && ri <= qr) {
lz1m[v] = (lz1m[v] * m) % md;
lz1d[v] = (lz1d[v] * d) % md;
relax1(v, le, ri);
return;
}
i64 mi = (le + ri) / 2;
rupdate1(le, mi, ql, qr, v * 2, m, d);
rupdate1(mi + 1, ri, ql, qr, v * 2 + 1, m, d);
st1[v] = (st1[v * 2] + st1[v * 2 + 1]) % md;
}
void pupdate1(i64 le, i64 ri, i64 ix, i64 v, i64 m, i64 d) {
relax1(v, le, ri);
if (le > ix || ri < ix) return;
if (le == ix && ix == ri) {
st1[v] = (st1[v] * m) % md;
st1[v] = (st1[v] * bp(d, md - 2)) % md;
return;
}
i64 mi = (le + ri) / 2;
pupdate1(le, mi, ix, v * 2, m, d);
pupdate1(mi + 1, ri, ix, v * 2 + 1, m, d);
st1[v] = (st1[v * 2] + st1[v * 2 + 1]) % md;
}
i64 query1(i64 le, i64 ri, i64 ix, i64 v) {
relax1(v, le, ri);
if (le > ix || ri < ix) return 0;
if (le == ix && ix == ri) {
return st1[v] % md;
}
i64 mi = (le + ri) / 2;
i64 lq = query1(le, mi, ix, v * 2);
i64 rq = query1(mi + 1, ri, ix, v * 2 + 1);
return (lq + rq) % md;
}
pair<ld, i64> marj(i64 v) {
auto& le = st2[v * 2];
auto& ri = st2[v * 2 + 1];
if (le.first >= ri.first) {
return le;
}
return ri;
}
void build2(i64 le, i64 ri, i64 v) {
if (le == ri) {
st2[v] = make_pair(d[le] + log10l(b[le]), le);
return;
}
i64 mi = (le + ri) / 2;
build2(le, mi, v * 2);
build2(mi + 1, ri, v * 2 + 1);
st2[v] = marj(v);
}
void relax2(i64 v, i64 le, i64 ri) {
if (lz2m[v] != 0 || lz2d[v] != 0) {
st2[v].first += lz2m[v];
st2[v].first -= lz2d[v];
if (le != ri) {
lz2m[v * 2] += lz2m[v];
lz2m[v * 2 + 1] += lz2m[v];
lz2d[v * 2] += lz2d[v];
lz2d[v * 2 + 1] += lz2d[v];
}
lz2m[v] = 0;
lz2d[v] = 0;
}
}
void rupdate2(i64 le, i64 ri, i64 ql, i64 qr, i64 v, ld m, ld d) {
relax2(v, le, ri);
if (le > qr || ri < ql) return;
if (ql <= le && ri <= qr) {
lz2m[v] += m;
lz2d[v] += d;
relax2(v, le, ri);
return;
}
i64 mi = (le + ri) / 2;
rupdate2(le, mi, ql, qr, v * 2, m, d);
rupdate2(mi + 1, ri, ql, qr, v * 2 + 1, m, d);
st2[v] = marj(v);
}
void pupdate2(i64 le, i64 ri, i64 ix, i64 v, ld m, ld d) {
relax2(v, le, ri);
if (le > ix || ri < ix) return;
if (le == ix && ri == ix) {
st2[v].first += m;
st2[v].first -= d;
return;
}
i64 mi = (le + ri) / 2;
pupdate2(le, mi, ix, v * 2, m, d);
pupdate2(mi + 1, ri, ix, v * 2 + 1, m, d);
st2[v] = marj(v);
}
int init(int N, int x[], int y[]) {
n = N;
c[0] = 1;
d[0] = 0;
for (i64 i = 1; i <= n; i++) {
a[i] = x[i - 1];
b[i] = y[i - 1];
c[i] = c[i - 1] * a[i] % md;
d[i] = d[i - 1] + log10l(a[i]);
}
build1(1, n, 1);
build2(1, n, 1);
i64 ix = st2[1].second;
return query1(1, n, ix, 1);
}
int updateX(int pos, int val) {
pos++;
rupdate1(1, n, pos, n, 1, val, a[pos]);
rupdate2(1, n, pos, n, 1, log10l(val), log10l(a[pos]));
a[pos] = val;
relax2(1, 1, n);
i64 ix = st2[1].second;
return query1(1, n, ix, 1);
}
int updateY(int pos, int val) {
pos++;
pupdate1(1, n, pos, 1, val, b[pos]);
pupdate2(1, n, pos, 1, log10l(val), log10l(b[pos]));
b[pos] = val;
relax2(1, 1, n);
i64 ix = st2[1].second;
return query1(1, n, ix, 1);
}
Compilation message
horses.cpp: In function 'long long int bp(long long int, long long int)':
horses.cpp:20:19: warning: declaration of 'b' shadows a global declaration [-Wshadow]
20 | i64 bp(i64 x, i64 b) {
| ^
horses.cpp:17:12: note: shadowed declaration is here
17 | i64 a[sz], b[sz], c[sz];
| ^
horses.cpp: In function 'void rupdate1(long long int, long long int, long long int, long long int, long long int, long long int, long long int)':
horses.cpp:58:65: warning: declaration of 'd' shadows a global declaration [-Wshadow]
58 | void rupdate1(i64 le, i64 ri, i64 ql, i64 qr, i64 v, i64 m, i64 d) {
| ^
horses.cpp:16:4: note: shadowed declaration is here
16 | ld d[sz];
| ^
horses.cpp: In function 'void pupdate1(long long int, long long int, long long int, long long int, long long int, long long int)':
horses.cpp:73:57: warning: declaration of 'd' shadows a global declaration [-Wshadow]
73 | void pupdate1(i64 le, i64 ri, i64 ix, i64 v, i64 m, i64 d) {
| ^
horses.cpp:16:4: note: shadowed declaration is here
16 | ld d[sz];
| ^
horses.cpp: In function 'void rupdate2(long long int, long long int, long long int, long long int, long long int, long double, long double)':
horses.cpp:134:63: warning: declaration of 'd' shadows a global declaration [-Wshadow]
134 | void rupdate2(i64 le, i64 ri, i64 ql, i64 qr, i64 v, ld m, ld d) {
| ^
horses.cpp:16:4: note: shadowed declaration is here
16 | ld d[sz];
| ^
horses.cpp: In function 'void pupdate2(long long int, long long int, long long int, long long int, long double, long double)':
horses.cpp:149:55: warning: declaration of 'd' shadows a global declaration [-Wshadow]
149 | void pupdate2(i64 le, i64 ri, i64 ix, i64 v, ld m, ld d) {
| ^
horses.cpp:16:4: note: shadowed declaration is here
16 | ld d[sz];
| ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:180:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
180 | return query1(1, n, ix, 1);
| ~~~~~~^~~~~~~~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:191:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
191 | return query1(1, n, ix, 1);
| ~~~~~~^~~~~~~~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:202:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
202 | return query1(1, n, ix, 1);
| ~~~~~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
14684 KB |
Output is correct |
2 |
Correct |
2 ms |
14680 KB |
Output is correct |
3 |
Correct |
1 ms |
14684 KB |
Output is correct |
4 |
Correct |
2 ms |
14936 KB |
Output is correct |
5 |
Correct |
2 ms |
14684 KB |
Output is correct |
6 |
Correct |
1 ms |
14684 KB |
Output is correct |
7 |
Correct |
1 ms |
14684 KB |
Output is correct |
8 |
Correct |
1 ms |
14684 KB |
Output is correct |
9 |
Correct |
2 ms |
14796 KB |
Output is correct |
10 |
Correct |
1 ms |
14684 KB |
Output is correct |
11 |
Correct |
1 ms |
14684 KB |
Output is correct |
12 |
Correct |
2 ms |
14936 KB |
Output is correct |
13 |
Correct |
1 ms |
14684 KB |
Output is correct |
14 |
Correct |
2 ms |
14684 KB |
Output is correct |
15 |
Correct |
1 ms |
14684 KB |
Output is correct |
16 |
Correct |
1 ms |
14684 KB |
Output is correct |
17 |
Correct |
1 ms |
14684 KB |
Output is correct |
18 |
Correct |
1 ms |
14684 KB |
Output is correct |
19 |
Correct |
1 ms |
14684 KB |
Output is correct |
20 |
Correct |
1 ms |
14684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
14684 KB |
Output is correct |
2 |
Correct |
2 ms |
14684 KB |
Output is correct |
3 |
Correct |
1 ms |
14684 KB |
Output is correct |
4 |
Correct |
1 ms |
14684 KB |
Output is correct |
5 |
Correct |
1 ms |
14680 KB |
Output is correct |
6 |
Correct |
1 ms |
14684 KB |
Output is correct |
7 |
Correct |
1 ms |
14684 KB |
Output is correct |
8 |
Correct |
1 ms |
14684 KB |
Output is correct |
9 |
Correct |
1 ms |
14684 KB |
Output is correct |
10 |
Correct |
2 ms |
14684 KB |
Output is correct |
11 |
Correct |
1 ms |
14680 KB |
Output is correct |
12 |
Correct |
1 ms |
14684 KB |
Output is correct |
13 |
Correct |
1 ms |
14684 KB |
Output is correct |
14 |
Correct |
2 ms |
14684 KB |
Output is correct |
15 |
Correct |
1 ms |
14684 KB |
Output is correct |
16 |
Correct |
1 ms |
14684 KB |
Output is correct |
17 |
Correct |
1 ms |
14684 KB |
Output is correct |
18 |
Correct |
1 ms |
14684 KB |
Output is correct |
19 |
Correct |
1 ms |
14684 KB |
Output is correct |
20 |
Correct |
1 ms |
14684 KB |
Output is correct |
21 |
Correct |
1 ms |
14684 KB |
Output is correct |
22 |
Correct |
1 ms |
14684 KB |
Output is correct |
23 |
Correct |
5 ms |
14684 KB |
Output is correct |
24 |
Correct |
5 ms |
14684 KB |
Output is correct |
25 |
Correct |
3 ms |
14864 KB |
Output is correct |
26 |
Correct |
4 ms |
14684 KB |
Output is correct |
27 |
Correct |
4 ms |
14684 KB |
Output is correct |
28 |
Correct |
4 ms |
14900 KB |
Output is correct |
29 |
Correct |
5 ms |
14888 KB |
Output is correct |
30 |
Correct |
6 ms |
14684 KB |
Output is correct |
31 |
Correct |
3 ms |
14908 KB |
Output is correct |
32 |
Correct |
3 ms |
14684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
163 ms |
89428 KB |
Output is correct |
2 |
Correct |
962 ms |
122448 KB |
Output is correct |
3 |
Correct |
930 ms |
122452 KB |
Output is correct |
4 |
Correct |
1153 ms |
122404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
14684 KB |
Output is correct |
2 |
Correct |
2 ms |
14684 KB |
Output is correct |
3 |
Correct |
1 ms |
14684 KB |
Output is correct |
4 |
Correct |
1 ms |
14684 KB |
Output is correct |
5 |
Correct |
1 ms |
14684 KB |
Output is correct |
6 |
Correct |
1 ms |
14684 KB |
Output is correct |
7 |
Correct |
1 ms |
14684 KB |
Output is correct |
8 |
Correct |
1 ms |
14684 KB |
Output is correct |
9 |
Correct |
2 ms |
14684 KB |
Output is correct |
10 |
Correct |
1 ms |
14684 KB |
Output is correct |
11 |
Correct |
1 ms |
14684 KB |
Output is correct |
12 |
Correct |
2 ms |
14684 KB |
Output is correct |
13 |
Correct |
1 ms |
14680 KB |
Output is correct |
14 |
Correct |
1 ms |
14684 KB |
Output is correct |
15 |
Correct |
1 ms |
14684 KB |
Output is correct |
16 |
Correct |
1 ms |
14684 KB |
Output is correct |
17 |
Correct |
1 ms |
14684 KB |
Output is correct |
18 |
Correct |
1 ms |
14684 KB |
Output is correct |
19 |
Correct |
1 ms |
14684 KB |
Output is correct |
20 |
Correct |
1 ms |
14684 KB |
Output is correct |
21 |
Correct |
1 ms |
14684 KB |
Output is correct |
22 |
Correct |
1 ms |
14684 KB |
Output is correct |
23 |
Correct |
5 ms |
14684 KB |
Output is correct |
24 |
Correct |
4 ms |
14680 KB |
Output is correct |
25 |
Correct |
3 ms |
14684 KB |
Output is correct |
26 |
Correct |
4 ms |
14684 KB |
Output is correct |
27 |
Correct |
3 ms |
14684 KB |
Output is correct |
28 |
Correct |
4 ms |
14912 KB |
Output is correct |
29 |
Correct |
6 ms |
14684 KB |
Output is correct |
30 |
Correct |
6 ms |
14684 KB |
Output is correct |
31 |
Correct |
2 ms |
14684 KB |
Output is correct |
32 |
Correct |
3 ms |
14684 KB |
Output is correct |
33 |
Correct |
156 ms |
121172 KB |
Output is correct |
34 |
Correct |
157 ms |
121172 KB |
Output is correct |
35 |
Correct |
82 ms |
88768 KB |
Output is correct |
36 |
Correct |
112 ms |
88656 KB |
Output is correct |
37 |
Correct |
99 ms |
105040 KB |
Output is correct |
38 |
Correct |
114 ms |
89552 KB |
Output is correct |
39 |
Correct |
124 ms |
89068 KB |
Output is correct |
40 |
Correct |
141 ms |
89428 KB |
Output is correct |
41 |
Correct |
60 ms |
90688 KB |
Output is correct |
42 |
Correct |
65 ms |
88660 KB |
Output is correct |
43 |
Correct |
64 ms |
88524 KB |
Output is correct |
44 |
Correct |
61 ms |
88612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
14680 KB |
Output is correct |
2 |
Correct |
1 ms |
14684 KB |
Output is correct |
3 |
Correct |
1 ms |
14684 KB |
Output is correct |
4 |
Correct |
1 ms |
14684 KB |
Output is correct |
5 |
Correct |
2 ms |
14684 KB |
Output is correct |
6 |
Correct |
1 ms |
14684 KB |
Output is correct |
7 |
Correct |
1 ms |
14684 KB |
Output is correct |
8 |
Correct |
1 ms |
14684 KB |
Output is correct |
9 |
Correct |
1 ms |
14684 KB |
Output is correct |
10 |
Correct |
1 ms |
14684 KB |
Output is correct |
11 |
Correct |
1 ms |
14684 KB |
Output is correct |
12 |
Correct |
1 ms |
14684 KB |
Output is correct |
13 |
Correct |
2 ms |
14684 KB |
Output is correct |
14 |
Correct |
1 ms |
14684 KB |
Output is correct |
15 |
Correct |
1 ms |
14684 KB |
Output is correct |
16 |
Correct |
1 ms |
14684 KB |
Output is correct |
17 |
Correct |
1 ms |
14684 KB |
Output is correct |
18 |
Correct |
1 ms |
14684 KB |
Output is correct |
19 |
Correct |
1 ms |
14684 KB |
Output is correct |
20 |
Correct |
2 ms |
14684 KB |
Output is correct |
21 |
Correct |
2 ms |
14684 KB |
Output is correct |
22 |
Correct |
1 ms |
14684 KB |
Output is correct |
23 |
Correct |
5 ms |
14684 KB |
Output is correct |
24 |
Correct |
5 ms |
14684 KB |
Output is correct |
25 |
Correct |
3 ms |
14684 KB |
Output is correct |
26 |
Correct |
4 ms |
14684 KB |
Output is correct |
27 |
Correct |
4 ms |
14684 KB |
Output is correct |
28 |
Correct |
4 ms |
14684 KB |
Output is correct |
29 |
Correct |
6 ms |
14684 KB |
Output is correct |
30 |
Correct |
6 ms |
14684 KB |
Output is correct |
31 |
Correct |
2 ms |
14684 KB |
Output is correct |
32 |
Correct |
3 ms |
14684 KB |
Output is correct |
33 |
Correct |
168 ms |
89552 KB |
Output is correct |
34 |
Correct |
916 ms |
122392 KB |
Output is correct |
35 |
Correct |
928 ms |
122448 KB |
Output is correct |
36 |
Correct |
1162 ms |
122452 KB |
Output is correct |
37 |
Correct |
166 ms |
121168 KB |
Output is correct |
38 |
Correct |
159 ms |
121080 KB |
Output is correct |
39 |
Correct |
99 ms |
88660 KB |
Output is correct |
40 |
Correct |
112 ms |
88660 KB |
Output is correct |
41 |
Correct |
102 ms |
104916 KB |
Output is correct |
42 |
Correct |
97 ms |
89424 KB |
Output is correct |
43 |
Correct |
114 ms |
88916 KB |
Output is correct |
44 |
Correct |
131 ms |
89428 KB |
Output is correct |
45 |
Correct |
56 ms |
90704 KB |
Output is correct |
46 |
Correct |
65 ms |
88824 KB |
Output is correct |
47 |
Correct |
58 ms |
88660 KB |
Output is correct |
48 |
Correct |
57 ms |
88660 KB |
Output is correct |
49 |
Correct |
774 ms |
122252 KB |
Output is correct |
50 |
Correct |
746 ms |
122252 KB |
Output is correct |
51 |
Correct |
205 ms |
89680 KB |
Output is correct |
52 |
Correct |
414 ms |
89684 KB |
Output is correct |
53 |
Correct |
603 ms |
106068 KB |
Output is correct |
54 |
Correct |
569 ms |
96144 KB |
Output is correct |
55 |
Correct |
749 ms |
89232 KB |
Output is correct |
56 |
Correct |
850 ms |
96340 KB |
Output is correct |
57 |
Correct |
153 ms |
91728 KB |
Output is correct |
58 |
Correct |
224 ms |
89680 KB |
Output is correct |
59 |
Correct |
61 ms |
88516 KB |
Output is correct |