#define Nhoksocqt1
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
template<class X, class Y>
inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 500005;
const int modl = 1e9+7;
ll fen[MAXN];
int X[MAXN], Y[MAXN], nArr;
#ifdef Nhoksocqt1
int init(int _N, int _X[], int _Y[]);
int updateX(int pos, int val);
int updateY(int pos, int val);
int _X[MAXN], _Y[MAXN];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
freopen("HORSES.inp", "r", stdin);
freopen("HORSES.out", "w", stdout);
int _N;
cin >> _N;
for (int i = 0; i < _N; ++i) {
cin >> _X[i];
//_X[i] = Random(1, 1e9); cout << _X[i] << " \n"[i + 1 == _N];
}
for (int i = 0; i < _N; ++i) {
cin >> _Y[i];
//_Y[i] = Random(1, 1e9); cout << _Y[i] << " \n"[i + 1 == _N];
}
cout << init(_N, _X, _Y) << '\n';
int Q;
cin >> Q;
while(Q--) {
int type, pos, val;
cin >> type >> pos >> val;
type = Random(0, 1), pos = Random(0, _N - 1), val = Random(1, 1e9); cout << type << ' ' << pos << ' ' << val << '\n';
if(type == 0) {
cout << updateX(pos, val) << '\n';
} else {
cout << updateY(pos, val) << '\n';
}
}
return 0;
}
#endif // Nhoksocqt1
ll powermod(ll a, int exponent) {
ll res(1);
while(exponent > 0) {
if(exponent & 1)
res = res * a % modl;
a = a * a % modl;
exponent >>= 1;
}
return res;
}
int segx[4 * MAXN], segy[4 * MAXN];
void build(int seg[], int id, int l, int r, int x[]) {
if(l == r) {
seg[id] = x[l];
return;
}
int mid = (l + r) >> 1;
build(seg, id << 1, l, mid, x);
build(seg, id << 1 | 1, mid + 1, r, x);
seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
}
void update(int seg[], int pos, int val) {
int id(1), l(1), r(nArr);
while(l != r) {
int mid = (l + r) >> 1;
if(pos <= mid) {
id = id << 1;
r = mid;
} else {
id = id << 1 | 1;
l = mid + 1;
}
}
seg[id] = val;
while(id > 1) {
id >>= 1;
seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
}
}
int findLast(int seg[], int id, int l, int r, int pos, int k) {
if(seg[id] < k || pos < l)
return 0;
if(r <= pos) {
while(l != r) {
int mid = (l + r) >> 1;
if(seg[id << 1 | 1] < k) {
id = id << 1;
r = mid;
} else {
id = id << 1 | 1;
l = mid + 1;
}
}
return l;
}
int mid = (l + r) >> 1;
return max(findLast(seg, id << 1, l, mid, pos, k), findLast(seg, id << 1 | 1, mid + 1, r, pos, k));
}
void modify(int i, int v) {
for (; i <= nArr; i += i & -i)
fen[i] = fen[i] * v % modl;
}
int get(int i) {
ll res(1);
for (; i > 0; i -= i & -i)
res = res * fen[i] % modl;
return res;
}
int query(int seg[], int id, int l, int r, int u, int v) {
if(v < l || u > r)
return 0;
if(u <= l && r <= v)
return seg[id];
int mid = (l + r) >> 1;
return max(query(seg, id << 1, l, mid, u, v), query(seg, id << 1 | 1, mid + 1, r, u, v));
}
typedef pair<ll, ll> pll;
int pos[MAXN];
int calc(void) {
pos[0] = nArr + 1;
ll prod(1);
int nPos(0), opt(nArr);
while(prod <= 1e9) {
prod *= X[opt];
pos[++nPos] = opt;
opt = findLast(segx, 1, 1, nArr, opt - 1, 2);
}
++nPos, prod = 1;
pll ansNow = {0, 0};
ll res = get(opt);
while(nPos--) {
int nxt = pos[nPos];
int maxY = query(segy, 1, 1, nArr, max(1, opt), nxt - 1);
if(!ansNow.se || double(ansNow.fi) / maxY < double(prod) / ansNow.se)
ansNow = {prod, maxY};
prod *= X[nxt];
opt = nxt;
}
ll ans = ansNow.fi % modl * ansNow.se % modl;
return res * ans % modl;
}
int init(int _N, int _X[], int _Y[]) {
nArr = _N;
for (int i = 1; i <= nArr; ++i) {
X[i] = _X[i - 1];
Y[i] = _Y[i - 1];
fen[i] = 1;
}
build(segx, 1, 1, nArr, X);
build(segy, 1, 1, nArr, Y);
for (int i = 1; i <= nArr; ++i)
modify(i, X[i]);
return calc();
}
int updateX(int pos, int val) {
++pos;
modify(pos, powermod(X[pos], modl - 2) * val % modl);
update(segx, pos, val);
X[pos] = val;
return calc();
}
int updateY(int pos, int val) {
++pos;
Y[pos] = val;
update(segy, pos, val);
return calc();
}
Compilation message
sorting.cpp: In function 'int get(int)':
sorting.cpp:158:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
158 | return res;
| ^~~
sorting.cpp: In function 'int calc()':
sorting.cpp:179:11: warning: conversion from 'll' {aka 'long long int'} to 'double' may change value [-Wconversion]
179 | while(prod <= 1e9) {
| ^~~~
sorting.cpp:8:12: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
8 | #define se second
| ^
sorting.cpp:191:75: note: in expansion of macro 'se'
191 | if(!ansNow.se || double(ansNow.fi) / maxY < double(prod) / ansNow.se)
| ^~
sorting.cpp:199:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
199 | return res * ans % modl;
| ~~~~~~~~~~^~~~~~
sorting.cpp: In function 'int init(int, int*, int*)':
sorting.cpp:202:32: warning: declaration of '_Y' shadows a global declaration [-Wshadow]
202 | int init(int _N, int _X[], int _Y[]) {
| ~~~~^~~~
sorting.cpp:36:15: note: shadowed declaration is here
36 | int _X[MAXN], _Y[MAXN];
| ^~
sorting.cpp:202:22: warning: declaration of '_X' shadows a global declaration [-Wshadow]
202 | int init(int _N, int _X[], int _Y[]) {
| ~~~~^~~~
sorting.cpp:36:5: note: shadowed declaration is here
36 | int _X[MAXN], _Y[MAXN];
| ^~
sorting.cpp: In function 'int updateX(int, int)':
sorting.cpp:218:17: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
218 | int updateX(int pos, int val) {
| ~~~~^~~
sorting.cpp:173:5: note: shadowed declaration is here
173 | int pos[MAXN];
| ^~~
sorting.cpp:220:50: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
220 | modify(pos, powermod(X[pos], modl - 2) * val % modl);
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
sorting.cpp: In function 'int updateY(int, int)':
sorting.cpp:227:17: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
227 | int updateY(int pos, int val) {
| ~~~~^~~
sorting.cpp:173:5: note: shadowed declaration is here
173 | int pos[MAXN];
| ^~~
sorting.cpp: In function 'int main()':
sorting.cpp:41:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | freopen("HORSES.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sorting.cpp:42:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | freopen("HORSES.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccwynC6Z.o: in function `main':
grader.c:(.text.startup+0x0): multiple definition of `main'; /tmp/ccNp7ta1.o:sorting.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccwynC6Z.o: in function `main':
grader.c:(.text.startup+0x4eb): undefined reference to `findSwapPairs(int, int*, int, int*, int*, int*, int*)'
collect2: error: ld returned 1 exit status
