/*************************************
* author: marvinthang *
* created: 08.03.2023 15:25:43 *
*************************************/
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define left ___left
#define right ___right
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define MASK(i) (1LL << (i))
#define BIT(x, i) ((x) >> (i) & 1)
#define __builtin_popcount __builtin_popcountll
#define ALL(v) (v).begin(), (v).end()
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define REPD(i, n) for (int i = (n); i--; )
#define FOR(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define FORD(i, b, a) for (int i = (b), _a = (a); --i >= _a; )
#define FORE(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORDE(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define scan_op(...) istream & operator >> (istream &in, __VA_ARGS__ &u)
#define print_op(...) ostream & operator << (ostream &out, const __VA_ARGS__ &u)
template <class T> scan_op(vector <T>) { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> scan_op(pair <U, V>) { return in >> u.fi >> u.se; }
template <class U, class V> print_op(pair <U, V>) { return out << '(' << u.first << ", " << u.second << ')'; }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")"; else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class T> T invGeneral(T a, T b) {
a %= b;
if (!a) return b == 1 ? 0 : -1;
T x = invGeneral(b, a);
return x == -1 ? -1 : ((1 - 1LL * b * x) / a + b) % b;
}
// end of template
const int MOD = 1e9 + 7;
const int MAX = 5e5 + 5;
int N, X[MAX], Y[MAX], bit[MAX], st[MAX << 2];
set <int, greater <int>> pos;
void build(int i, int l, int r) {
if (r - l == 1) {
st[i] = Y[l];
return;
}
int m = l + r >> 1;
build(i << 1, l, m);
build(i << 1 | 1, m, r);
st[i] = max(st[i << 1], st[i << 1 | 1]);
}
void update(int i, int l, int r, int p) {
if (r - l == 1) {
st[i] = Y[l];
return;
}
int m = l + r >> 1;
if (p < m) update(i << 1, l, m, p);
else update(i << 1 | 1, m, r, p);
st[i] = max(st[i << 1], st[i << 1 | 1]);
}
int getMax(int i, int l, int r, int u, int v) {
if (l >= v || r <= u) return 0;
if (u <= l && r <= v) return st[i];
int m = l + r >> 1;
return max(getMax(i << 1, l, m, u, v), getMax(i << 1 | 1, m, r, u, v));
}
void update(int i, int v) {
for (++i; i <= N; i += i & -i) bit[i] = 1LL * bit[i] * v % MOD;
}
int getMul(int i) {
int res = 1;
for (++i; i > 0; i &= i - 1) res = 1LL * res * bit[i] % MOD;
return res;
}
int solve(void) {
int res = -1;
long long cb = 1;
int r = N, ma = 0, mb = 0;
cout << getMul(2) << '\n';
for (int l: pos) {
int ca = getMax(1, 0, N, l, r);
// ma / ca * cb / mb > 1
// ma * cb > ca * mb
if (1LL * ca * mb >= 1LL * ma * cb) {
res = 1LL * getMul(l) * ca % MOD;
ma = ca; mb = cb;
}
// cout << l << ' ' << r << ' ' << ca << ' ' << cb << ' ' << res << '\n';
cb *= X[l];
if (cb > MOD) break;
r = l;
}
// cout << "-------\n";
return res;
}
int init(int n, int x[], int y[]) {
N = n;
fill(bit, bit + N + 1, 1);
REP(i, N) {
X[i] = x[i]; Y[i] = y[i];
if (!i || X[i] != 1) {
update(i, X[i]);
pos.insert(i);
}
}
build(1, 0, N);
return solve();
}
int updateX(int i, int val) {
if (X[i] != 1) {
update(i, invGeneral(X[i], MOD));
pos.erase(i);
}
X[i] = val;
if (!i || X[i] != 1) {
update(i, X[i]);
pos.insert(i);
}
return solve();
}
int updateY(int i, int val) {
Y[i] = val;
update(1, 0, N, i);
return solve();
}
#ifdef LOCAL
static char _buffer[1024];
static int _currentChar = 0;
static int _charsNumber = 0;
static FILE *_inputFile, *_outputFile;
static inline int _read() {
if (_charsNumber < 0) {
exit(1);
}
if (!_charsNumber || _currentChar == _charsNumber) {
_charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile);
_currentChar = 0;
}
if (_charsNumber <= 0) {
return -1;
}
return _buffer[_currentChar++];
}
static inline int _readInt() {
int c, x, s;
c = _read();
while (c <= 32) c = _read();
x = 0;
s = 1;
if (c == '-') {
s = -1;
c = _read();
}
while (c > 32) {
x *= 10;
x += c - '0';
c = _read();
}
if (s < 0) x = -x;
return x;
}
int main() {
_inputFile = fopen("horses.in", "rb");
_outputFile = fopen("horses.out", "w");
int N; N = _readInt();
int *X = (int*)malloc(sizeof(int)*(unsigned int)N);
int *Y = (int*)malloc(sizeof(int)*(unsigned int)N);
for (int i = 0; i < N; i++) {
X[i] = _readInt();
}
for (int i = 0; i < N; i++) {
Y[i] = _readInt();
}
fprintf(_outputFile,"%d\n",init(N,X,Y));
int M; M = _readInt();
for (int i = 0; i < M; i++) {
int type; type = _readInt();
int pos; pos = _readInt();
int val; val = _readInt();
if (type == 1) {
fprintf(_outputFile,"%d\n",updateX(pos,val));
} else if (type == 2) {
fprintf(_outputFile,"%d\n",updateY(pos,val));
}
}
return 0;
}
#endif
Compilation message
horses.cpp: In function 'void build(int, int, int)':
horses.cpp:55:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
55 | int m = l + r >> 1;
| ~~^~~
horses.cpp: In function 'void update(int, int, int, int)':
horses.cpp:66:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
66 | int m = l + r >> 1;
| ~~^~~
horses.cpp: In function 'int getMax(int, int, int, int, int)':
horses.cpp:75:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
75 | int m = l + r >> 1;
| ~~^~~
horses.cpp: In function 'void update(int, int)':
horses.cpp:80:59: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
80 | for (++i; i <= N; i += i & -i) bit[i] = 1LL * bit[i] * v % MOD;
| ~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int getMul(int)':
horses.cpp:85:56: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
85 | for (++i; i > 0; i &= i - 1) res = 1LL * res * bit[i] % MOD;
| ~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int solve()':
horses.cpp:99:31: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
99 | res = 1LL * getMul(l) * ca % MOD;
| ~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:100:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
100 | ma = ca; mb = cb;
| ^~
horses.cpp: In instantiation of 'T invGeneral(T, T) [with T = int]':
horses.cpp:127:33: required from here
horses.cpp:39:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
39 | return x == -1 ? -1 : ((1 - 1LL * b * x) / a + b) % b;
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
584 ms |
42624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
