#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) {
if (0 == b) return 1;
i64 r = bp(x, b >> 1) % md;
r = (r * r) % md;
if (b & 1) return (r * x) % md;
return r;
}
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:56:65: warning: declaration of 'd' shadows a global declaration [-Wshadow]
56 | 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:71:57: warning: declaration of 'd' shadows a global declaration [-Wshadow]
71 | 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:132:63: warning: declaration of 'd' shadows a global declaration [-Wshadow]
132 | 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:147:55: warning: declaration of 'd' shadows a global declaration [-Wshadow]
147 | 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:178:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
178 | return query1(1, n, ix, 1);
| ~~~~~~^~~~~~~~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:189:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
189 | return query1(1, n, ix, 1);
| ~~~~~~^~~~~~~~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:200:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
200 | return query1(1, n, ix, 1);
| ~~~~~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
14680 KB |
Output is correct |
2 |
Correct |
1 ms |
14680 KB |
Output is correct |
3 |
Correct |
1 ms |
14684 KB |
Output is correct |
4 |
Correct |
2 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 |
1 ms |
14684 KB |
Output is correct |
10 |
Correct |
1 ms |
14684 KB |
Output is correct |
11 |
Correct |
2 ms |
14684 KB |
Output is correct |
12 |
Correct |
1 ms |
14684 KB |
Output is correct |
13 |
Correct |
1 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 |
14680 KB |
Output is correct |
17 |
Correct |
2 ms |
14684 KB |
Output is correct |
18 |
Correct |
1 ms |
14684 KB |
Output is correct |
19 |
Correct |
1 ms |
14680 KB |
Output is correct |
20 |
Correct |
1 ms |
14684 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 |
1 ms |
14684 KB |
Output is correct |
6 |
Correct |
2 ms |
14684 KB |
Output is correct |
7 |
Correct |
1 ms |
14684 KB |
Output is correct |
8 |
Correct |
2 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 |
14684 KB |
Output is correct |
12 |
Correct |
1 ms |
14684 KB |
Output is correct |
13 |
Correct |
1 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 |
1 ms |
14684 KB |
Output is correct |
22 |
Correct |
2 ms |
14680 KB |
Output is correct |
23 |
Correct |
5 ms |
14904 KB |
Output is correct |
24 |
Correct |
5 ms |
14684 KB |
Output is correct |
25 |
Correct |
2 ms |
14684 KB |
Output is correct |
26 |
Correct |
4 ms |
14684 KB |
Output is correct |
27 |
Correct |
4 ms |
14680 KB |
Output is correct |
28 |
Correct |
5 ms |
14684 KB |
Output is correct |
29 |
Correct |
7 ms |
14888 KB |
Output is correct |
30 |
Correct |
8 ms |
14684 KB |
Output is correct |
31 |
Correct |
2 ms |
14684 KB |
Output is correct |
32 |
Correct |
3 ms |
14684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
161 ms |
89552 KB |
Output is correct |
2 |
Correct |
1267 ms |
122328 KB |
Output is correct |
3 |
Correct |
1255 ms |
122448 KB |
Output is correct |
4 |
Execution timed out |
1544 ms |
122132 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
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 |
2 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 |
1 ms |
14684 KB |
Output is correct |
14 |
Correct |
1 ms |
14936 KB |
Output is correct |
15 |
Correct |
2 ms |
14684 KB |
Output is correct |
16 |
Correct |
1 ms |
14684 KB |
Output is correct |
17 |
Correct |
1 ms |
14788 KB |
Output is correct |
18 |
Correct |
2 ms |
14680 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 |
6 ms |
14904 KB |
Output is correct |
24 |
Correct |
6 ms |
14680 KB |
Output is correct |
25 |
Correct |
4 ms |
14680 KB |
Output is correct |
26 |
Correct |
4 ms |
14868 KB |
Output is correct |
27 |
Correct |
4 ms |
14784 KB |
Output is correct |
28 |
Correct |
4 ms |
14684 KB |
Output is correct |
29 |
Correct |
7 ms |
14684 KB |
Output is correct |
30 |
Correct |
7 ms |
14684 KB |
Output is correct |
31 |
Correct |
2 ms |
14684 KB |
Output is correct |
32 |
Correct |
5 ms |
14876 KB |
Output is correct |
33 |
Correct |
184 ms |
121288 KB |
Output is correct |
34 |
Correct |
166 ms |
121168 KB |
Output is correct |
35 |
Correct |
78 ms |
88624 KB |
Output is correct |
36 |
Correct |
127 ms |
88660 KB |
Output is correct |
37 |
Correct |
123 ms |
104912 KB |
Output is correct |
38 |
Correct |
114 ms |
89424 KB |
Output is correct |
39 |
Correct |
135 ms |
88916 KB |
Output is correct |
40 |
Correct |
173 ms |
89324 KB |
Output is correct |
41 |
Correct |
53 ms |
90704 KB |
Output is correct |
42 |
Correct |
68 ms |
88656 KB |
Output is correct |
43 |
Correct |
57 ms |
88660 KB |
Output is correct |
44 |
Correct |
53 ms |
88608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
14680 KB |
Output is correct |
2 |
Correct |
1 ms |
14680 KB |
Output is correct |
3 |
Correct |
1 ms |
14684 KB |
Output is correct |
4 |
Correct |
1 ms |
14796 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 |
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 |
14680 KB |
Output is correct |
13 |
Correct |
1 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 |
1 ms |
14684 KB |
Output is correct |
21 |
Correct |
1 ms |
14684 KB |
Output is correct |
22 |
Correct |
2 ms |
14684 KB |
Output is correct |
23 |
Correct |
6 ms |
14684 KB |
Output is correct |
24 |
Correct |
6 ms |
14684 KB |
Output is correct |
25 |
Correct |
3 ms |
14684 KB |
Output is correct |
26 |
Correct |
4 ms |
14860 KB |
Output is correct |
27 |
Correct |
6 ms |
14684 KB |
Output is correct |
28 |
Correct |
5 ms |
14684 KB |
Output is correct |
29 |
Correct |
7 ms |
14684 KB |
Output is correct |
30 |
Correct |
8 ms |
14904 KB |
Output is correct |
31 |
Correct |
3 ms |
14684 KB |
Output is correct |
32 |
Correct |
4 ms |
14684 KB |
Output is correct |
33 |
Correct |
146 ms |
89684 KB |
Output is correct |
34 |
Correct |
1333 ms |
122480 KB |
Output is correct |
35 |
Correct |
1250 ms |
122456 KB |
Output is correct |
36 |
Execution timed out |
1562 ms |
122196 KB |
Time limit exceeded |
37 |
Halted |
0 ms |
0 KB |
- |