#include <bits/stdc++.h>
using namespace std;
#define lol long long
const lol maxn = 5e5 + 5, maxN = 2e6 + 5, M = 1e9 + 7, MX = INT_MAX;
lol pwr(lol val, lol p) {
if (p==0) return 1;
lol cur = pwr(val, p/2);
cur = cur * cur % M;
if (p%2==1) cur = cur * val % M;
return cur;
}
lol n, x[maxn], y[maxn], all;
lol seg[maxN];
void build(int id, int l, int r) {
if (l==r) {
seg[id] = y[l];
return;
}
int mid = (l+r)/2;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
seg[id] = max(seg[id*2], seg[id*2+1]);
}
void update(int id, int l, int r, int target, int val) {
if (r<target || target<l) return;
if (l==r) {
seg[id] = val;
return;
}
int mid = (l+r)/2;
update(id*2, l, mid, target, val);
update(id*2+1, mid+1, r, target, val);
seg[id] = max(seg[id*2], seg[id*2+1]);
}
lol mx(int id, int l, int r, int findl, int findr) {
if (r<findl || findr<l) return 0;
if (findl<=l && r<=findr) return seg[id];
int mid = (l+r)/2;
return max(mx(id*2, l, mid, findl, findr), mx(id*2+1, mid+1, r, findl, findr));
}
set<int> s;
int32_t solve() {
auto it = next(s.rbegin());
lol cnt1 = 1;
if (*it==-1) return mx(1, 0, n-1, 0, n-1);
while (cnt1 <= MX) {
cnt1 *= x[*it];
it = next(it);
if (*it==-1) break;
}
lol ans = 1;
if (*it == -1) {
it = prev(it);
ans = max(mx(1, 0, n-1, 0, *it-1), ans);
// cout << ans << endl;
}
lol cnt2 = 1;
while (it != s.rbegin()) {
cnt2 *= x[*it];
ans = max(mx(1, 0, n-1, *it, *prev(it) - 1) * cnt2, ans);
// cout << *it << " " << *prev(it)-1 << " " << mx(1, 0, n-1, *it, *prev(it) - 1) << " " << cnt2 << endl;
it = prev(it);
}
ans %= M;
ans = ans * (all * pwr(cnt1, M-2) % M) % M;
return ans;
}
lol init(int N, lol X[], lol Y[]) {
n = N;
all = 1;
s.insert(-1);
s.insert(n);
for (int i=0;i<n;i++) {
x[i] = X[i], y[i] = Y[i];
all = all * x[i] % M;
if (x[i]!=1) s.insert(i);
}
build(1, 0, n-1);
return solve();
}
lol updateX(int pos, lol val) {
if (val==1) s.erase(pos);
// cout << x[pos] << " " << val << endl;
if (x[pos]==1 && val!=1) {
s.insert(pos);
// cout << "test" << endl;
}
all = all * pwr(x[pos], M-2) % M;
x[pos] = val;
all = all * val % M;
return solve();
}
lol updateY(int pos, lol val) {
update(1, 0, n-1, pos, val);
return solve();
}
Compilation message
horses.cpp: In function 'int32_t solve()':
horses.cpp:49:35: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
49 | if (*it==-1) return mx(1, 0, n-1, 0, n-1);
| ~^~
horses.cpp:49:43: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
49 | if (*it==-1) return mx(1, 0, n-1, 0, n-1);
| ~^~
horses.cpp:49:27: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
49 | if (*it==-1) return mx(1, 0, n-1, 0, n-1);
| ~~^~~~~~~~~~~~~~~~~~~
horses.cpp:58:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
58 | ans = max(mx(1, 0, n-1, 0, *it-1), ans);
| ~^~
horses.cpp:64:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
64 | ans = max(mx(1, 0, n-1, *it, *prev(it) - 1) * cnt2, ans);
| ~^~
horses.cpp:70:12: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
70 | return ans;
| ^~~
horses.cpp: In function 'long long int init(int, long long int*, long long int*)':
horses.cpp:77:14: warning: conversion from 'long long int' to 'std::set<int>::value_type' {aka 'int'} may change value [-Wconversion]
77 | s.insert(n);
| ^
horses.cpp:83:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
83 | build(1, 0, n-1);
| ~^~
horses.cpp: In function 'long long int updateY(int, long long int)':
horses.cpp:101:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
101 | update(1, 0, n-1, pos, val);
| ~^~
horses.cpp:101:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
101 | update(1, 0, n-1, pos, val);
| ^~~
/usr/bin/ld: /tmp/ccx458UP.o: in function `main':
grader.c:(.text.startup+0xaa): undefined reference to `init(int, int*, int*)'
/usr/bin/ld: grader.c:(.text.startup+0x113): undefined reference to `updateX(int, int)'
/usr/bin/ld: grader.c:(.text.startup+0x16d): undefined reference to `updateY(int, int)'
collect2: error: ld returned 1 exit status
