#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
#include "horses.h"
const int MAX_N = 500010, p = 1e9 + 7;
const ll inf = p;
//ll dp[MAX_N], mdp[MAX_N];
int sx[MAX_N], sy[MAX_N], n;
struct dint {
ll val, mod_val;
dint (ll a, ll b) : val(a), mod_val(b) {}
dint () : val(0), mod_val(0) {}
#define fastop(op) dint &operator op (const dint &b) { val = min(inf, (val op b.val)), mod_val = val op b.val % p; return *this; }
fastop(*=);
fastop(+=);
dint operator + (const dint &b) {
dint x = *this;
x += b;
return x;
}
dint operator * (const dint &b) {
dint x = *this;
x *= b;
return x;
}
bool operator < (dint b) { return val < b.val; }
// dint &operator *= (dint b) {
// val
};
struct node {
ll mod_mxv, mod_mulx, lx, rx, ay;
node(ll x, ll y) {
mod_mxv = x * y % p;
mod_mulx = x;
lx = x, rx = 1;
ay = y;
}
node () {
mod_mxv = 1, mod_mulx = 1, lx = 1, rx = 1, ay = 1;
}
node (node a, node b) {
if (min(inf, a.rx * b.lx) * b.ay > a.ay) {
lx = min(inf, min(inf, a.lx * a.rx) * b.lx);
rx = b.rx;
ay = b.ay;
mod_mxv = b.mod_mxv * a.mod_mulx % p;
}
else {
lx = a.lx;
rx = min(inf, min(inf, b.lx * b.rx) * a.rx);
ay = a.ay;
mod_mxv = a.mod_mxv;
}
mod_mulx = a.mod_mulx * b.mod_mulx % p;
}
ll get() { return mod_mxv; }
};
//node dp[MAX_N];
node val[MAX_N << 1];
void modify(int i) {
val[i+n] = node(sx[i], sy[i]);
i += n;
while (i>>=1)
val[i] = node(val[i<<1], val[i<<1|1]);
}
int qry(int l, int r) {
l += n, r += n;
node lv, rv;
for (;l < r;l>>=1, r>>=1) {
if (l&1) lv = node(lv, val[l++]);
if (r&1) rv = node(val[--r], rv);
}
return node(lv, rv).get();
}
int init(int N, int X[], int Y[]) {
n = N;
copy(X, X+n, sx);
copy(Y, Y+n, sy);
for (int i = n-1;i >= 0;--i) {
modify(i);
//dp[i] = node( node(sx[i], sy[i]), dp[i+1] );
}
return qry(0, n);
//return dp[0].get();
}
int updateX(int pos, int val) {
sx[pos] = val;
modify(pos);
// for (int i = n-1;i >= 0;--i) {
// dp[i] = node( node(sx[i], sy[i]), dp[i+1] );
// }
return qry(0, n);
//return dp[0].get();
}
int updateY(int pos, int val) {
sy[pos] = val;
modify(pos);
// for (int i = n-1;i >= 0;--i) {
// dp[i] = node( node(sx[i], sy[i]), dp[i+1] );
// }
return qry(0, n);
//return dp[0].get();
}
Compilation message
horses.cpp: In member function 'dint& dint::operator*=(const dint&)':
horses.cpp:30:60: warning: operation on '((dint*)this)->dint::val' may be undefined [-Wsequence-point]
30 | #define fastop(op) dint &operator op (const dint &b) { val = min(inf, (val op b.val)), mod_val = val op b.val % p; return *this; }
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:31:2: note: in expansion of macro 'fastop'
31 | fastop(*=);
| ^~~~~~
horses.cpp: In member function 'dint& dint::operator+=(const dint&)':
horses.cpp:30:60: warning: operation on '((dint*)this)->dint::val' may be undefined [-Wsequence-point]
30 | #define fastop(op) dint &operator op (const dint &b) { val = min(inf, (val op b.val)), mod_val = val op b.val % p; return *this; }
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:32:2: note: in expansion of macro 'fastop'
32 | fastop(+=);
| ^~~~~~
horses.cpp: In function 'int qry(int, int)':
horses.cpp:93:25: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
93 | return node(lv, rv).get();
| ~~~~~~~~~~~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:108:26: warning: declaration of 'val' shadows a global declaration [-Wshadow]
108 | int updateX(int pos, int val) {
| ~~~~^~~
horses.cpp:78:6: note: shadowed declaration is here
78 | node val[MAX_N << 1];
| ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:118:26: warning: declaration of 'val' shadows a global declaration [-Wshadow]
118 | int updateY(int pos, int val) {
| ~~~~^~~
horses.cpp:78:6: note: shadowed declaration is here
78 | node val[MAX_N << 1];
| ^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
39372 KB |
Output is correct |
2 |
Correct |
24 ms |
39424 KB |
Output is correct |
3 |
Correct |
25 ms |
39436 KB |
Output is correct |
4 |
Correct |
25 ms |
39420 KB |
Output is correct |
5 |
Correct |
25 ms |
39344 KB |
Output is correct |
6 |
Correct |
22 ms |
39380 KB |
Output is correct |
7 |
Correct |
25 ms |
39364 KB |
Output is correct |
8 |
Correct |
25 ms |
39372 KB |
Output is correct |
9 |
Correct |
22 ms |
39444 KB |
Output is correct |
10 |
Correct |
23 ms |
39416 KB |
Output is correct |
11 |
Correct |
21 ms |
39440 KB |
Output is correct |
12 |
Correct |
25 ms |
39412 KB |
Output is correct |
13 |
Correct |
21 ms |
39372 KB |
Output is correct |
14 |
Correct |
25 ms |
39372 KB |
Output is correct |
15 |
Correct |
22 ms |
39372 KB |
Output is correct |
16 |
Correct |
22 ms |
39444 KB |
Output is correct |
17 |
Correct |
23 ms |
39444 KB |
Output is correct |
18 |
Correct |
22 ms |
39436 KB |
Output is correct |
19 |
Correct |
20 ms |
39372 KB |
Output is correct |
20 |
Correct |
19 ms |
39436 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
39372 KB |
Output is correct |
2 |
Correct |
20 ms |
39372 KB |
Output is correct |
3 |
Correct |
23 ms |
39456 KB |
Output is correct |
4 |
Correct |
21 ms |
39372 KB |
Output is correct |
5 |
Correct |
22 ms |
39444 KB |
Output is correct |
6 |
Correct |
19 ms |
39408 KB |
Output is correct |
7 |
Correct |
22 ms |
39364 KB |
Output is correct |
8 |
Correct |
23 ms |
39428 KB |
Output is correct |
9 |
Correct |
19 ms |
39444 KB |
Output is correct |
10 |
Correct |
19 ms |
39436 KB |
Output is correct |
11 |
Correct |
22 ms |
39452 KB |
Output is correct |
12 |
Correct |
23 ms |
39444 KB |
Output is correct |
13 |
Correct |
24 ms |
39372 KB |
Output is correct |
14 |
Correct |
24 ms |
39440 KB |
Output is correct |
15 |
Correct |
23 ms |
39372 KB |
Output is correct |
16 |
Correct |
22 ms |
39440 KB |
Output is correct |
17 |
Correct |
23 ms |
39372 KB |
Output is correct |
18 |
Correct |
24 ms |
39444 KB |
Output is correct |
19 |
Correct |
20 ms |
39376 KB |
Output is correct |
20 |
Correct |
21 ms |
39332 KB |
Output is correct |
21 |
Correct |
24 ms |
39372 KB |
Output is correct |
22 |
Correct |
21 ms |
39428 KB |
Output is correct |
23 |
Correct |
20 ms |
39372 KB |
Output is correct |
24 |
Correct |
20 ms |
39484 KB |
Output is correct |
25 |
Correct |
21 ms |
39500 KB |
Output is correct |
26 |
Correct |
20 ms |
39452 KB |
Output is correct |
27 |
Correct |
20 ms |
39424 KB |
Output is correct |
28 |
Correct |
23 ms |
39420 KB |
Output is correct |
29 |
Correct |
20 ms |
39472 KB |
Output is correct |
30 |
Correct |
21 ms |
39372 KB |
Output is correct |
31 |
Correct |
21 ms |
39456 KB |
Output is correct |
32 |
Correct |
21 ms |
39468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
173 ms |
52016 KB |
Output is correct |
2 |
Correct |
267 ms |
60780 KB |
Output is correct |
3 |
Correct |
233 ms |
52052 KB |
Output is correct |
4 |
Correct |
260 ms |
55832 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
39404 KB |
Output is correct |
2 |
Correct |
22 ms |
39372 KB |
Output is correct |
3 |
Correct |
26 ms |
39372 KB |
Output is correct |
4 |
Correct |
27 ms |
39456 KB |
Output is correct |
5 |
Correct |
24 ms |
39352 KB |
Output is correct |
6 |
Correct |
21 ms |
39416 KB |
Output is correct |
7 |
Correct |
24 ms |
39340 KB |
Output is correct |
8 |
Correct |
26 ms |
39336 KB |
Output is correct |
9 |
Correct |
22 ms |
39372 KB |
Output is correct |
10 |
Correct |
23 ms |
39436 KB |
Output is correct |
11 |
Correct |
22 ms |
39332 KB |
Output is correct |
12 |
Correct |
24 ms |
39364 KB |
Output is correct |
13 |
Correct |
22 ms |
39352 KB |
Output is correct |
14 |
Correct |
26 ms |
39440 KB |
Output is correct |
15 |
Correct |
22 ms |
39372 KB |
Output is correct |
16 |
Correct |
22 ms |
39388 KB |
Output is correct |
17 |
Correct |
22 ms |
39364 KB |
Output is correct |
18 |
Correct |
22 ms |
39372 KB |
Output is correct |
19 |
Correct |
22 ms |
39444 KB |
Output is correct |
20 |
Correct |
21 ms |
39456 KB |
Output is correct |
21 |
Correct |
22 ms |
39368 KB |
Output is correct |
22 |
Correct |
20 ms |
39344 KB |
Output is correct |
23 |
Correct |
21 ms |
39372 KB |
Output is correct |
24 |
Correct |
23 ms |
39500 KB |
Output is correct |
25 |
Correct |
21 ms |
39500 KB |
Output is correct |
26 |
Correct |
23 ms |
39448 KB |
Output is correct |
27 |
Correct |
23 ms |
39392 KB |
Output is correct |
28 |
Correct |
20 ms |
39396 KB |
Output is correct |
29 |
Correct |
22 ms |
39360 KB |
Output is correct |
30 |
Correct |
22 ms |
39500 KB |
Output is correct |
31 |
Correct |
23 ms |
39472 KB |
Output is correct |
32 |
Correct |
22 ms |
39372 KB |
Output is correct |
33 |
Correct |
155 ms |
51236 KB |
Output is correct |
34 |
Correct |
152 ms |
51324 KB |
Output is correct |
35 |
Correct |
169 ms |
58204 KB |
Output is correct |
36 |
Correct |
172 ms |
58060 KB |
Output is correct |
37 |
Correct |
140 ms |
49356 KB |
Output is correct |
38 |
Correct |
138 ms |
50268 KB |
Output is correct |
39 |
Correct |
135 ms |
49312 KB |
Output is correct |
40 |
Correct |
169 ms |
53168 KB |
Output is correct |
41 |
Correct |
123 ms |
49296 KB |
Output is correct |
42 |
Correct |
124 ms |
49340 KB |
Output is correct |
43 |
Correct |
157 ms |
53528 KB |
Output is correct |
44 |
Correct |
147 ms |
53596 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
39336 KB |
Output is correct |
2 |
Correct |
23 ms |
39376 KB |
Output is correct |
3 |
Correct |
23 ms |
39388 KB |
Output is correct |
4 |
Correct |
26 ms |
39376 KB |
Output is correct |
5 |
Correct |
22 ms |
39340 KB |
Output is correct |
6 |
Correct |
22 ms |
39372 KB |
Output is correct |
7 |
Correct |
22 ms |
39424 KB |
Output is correct |
8 |
Correct |
22 ms |
39444 KB |
Output is correct |
9 |
Correct |
24 ms |
39444 KB |
Output is correct |
10 |
Correct |
25 ms |
39432 KB |
Output is correct |
11 |
Correct |
22 ms |
39372 KB |
Output is correct |
12 |
Correct |
22 ms |
39364 KB |
Output is correct |
13 |
Correct |
23 ms |
39500 KB |
Output is correct |
14 |
Correct |
22 ms |
39376 KB |
Output is correct |
15 |
Correct |
23 ms |
39424 KB |
Output is correct |
16 |
Correct |
25 ms |
39372 KB |
Output is correct |
17 |
Correct |
23 ms |
39440 KB |
Output is correct |
18 |
Correct |
23 ms |
39364 KB |
Output is correct |
19 |
Correct |
20 ms |
39392 KB |
Output is correct |
20 |
Correct |
23 ms |
39452 KB |
Output is correct |
21 |
Correct |
23 ms |
39404 KB |
Output is correct |
22 |
Correct |
22 ms |
39372 KB |
Output is correct |
23 |
Correct |
24 ms |
39456 KB |
Output is correct |
24 |
Correct |
25 ms |
39468 KB |
Output is correct |
25 |
Correct |
25 ms |
39404 KB |
Output is correct |
26 |
Correct |
25 ms |
39452 KB |
Output is correct |
27 |
Correct |
23 ms |
39480 KB |
Output is correct |
28 |
Correct |
24 ms |
39372 KB |
Output is correct |
29 |
Correct |
23 ms |
39448 KB |
Output is correct |
30 |
Correct |
23 ms |
39372 KB |
Output is correct |
31 |
Correct |
23 ms |
39444 KB |
Output is correct |
32 |
Correct |
23 ms |
39372 KB |
Output is correct |
33 |
Correct |
184 ms |
51976 KB |
Output is correct |
34 |
Correct |
287 ms |
60808 KB |
Output is correct |
35 |
Correct |
253 ms |
51908 KB |
Output is correct |
36 |
Correct |
260 ms |
55896 KB |
Output is correct |
37 |
Correct |
156 ms |
51252 KB |
Output is correct |
38 |
Correct |
166 ms |
51252 KB |
Output is correct |
39 |
Correct |
174 ms |
58108 KB |
Output is correct |
40 |
Correct |
177 ms |
58064 KB |
Output is correct |
41 |
Correct |
147 ms |
49356 KB |
Output is correct |
42 |
Correct |
141 ms |
50284 KB |
Output is correct |
43 |
Correct |
123 ms |
49228 KB |
Output is correct |
44 |
Correct |
156 ms |
53256 KB |
Output is correct |
45 |
Correct |
143 ms |
49300 KB |
Output is correct |
46 |
Correct |
123 ms |
49380 KB |
Output is correct |
47 |
Correct |
160 ms |
53628 KB |
Output is correct |
48 |
Correct |
147 ms |
53684 KB |
Output is correct |
49 |
Correct |
254 ms |
53188 KB |
Output is correct |
50 |
Correct |
251 ms |
53304 KB |
Output is correct |
51 |
Correct |
215 ms |
59972 KB |
Output is correct |
52 |
Correct |
208 ms |
59484 KB |
Output is correct |
53 |
Correct |
231 ms |
51604 KB |
Output is correct |
54 |
Correct |
182 ms |
52056 KB |
Output is correct |
55 |
Correct |
158 ms |
50408 KB |
Output is correct |
56 |
Correct |
190 ms |
55048 KB |
Output is correct |
57 |
Correct |
163 ms |
50976 KB |
Output is correct |
58 |
Correct |
167 ms |
51472 KB |
Output is correct |
59 |
Correct |
148 ms |
53524 KB |
Output is correct |