#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
const int MOD = 1e9 + 7;
int bigmod(int b, int p) {
b %= MOD;
int res = 1;
while (p) {
if (p & 1) res = (res * b) % MOD;
p >>= 1; b = (b * b) % MOD;
}
return res;
}
int modinv(int x) {
return bigmod(x, MOD - 2);
}
const int mxN = 5e5 + 1;
int seg[(1 << 20)];
pii a[mxN];
int n;
void build(int l = 1, int r = n, int idx = 1) {
if (l == r) {
seg[idx] = a[l].ss;
return;
}
int mid = (l + r) >> 1;
build(l, mid, (idx << 1));
build(mid + 1, r, (idx << 1) | 1);
seg[idx] = max(seg[(idx << 1)], seg[(idx << 1) | 1]);
}
void update(int pos, int val, int l = 1, int r = n, int idx = 1) {
if (l == r) {
seg[idx] = val;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) update(pos, val, l, mid, (idx << 1));
else update(pos, val, mid + 1, r, (idx << 1) | 1);
seg[idx] = max(seg[(idx << 1)], seg[(idx << 1) | 1]);
}
int query(int tl, int tr, int l = 1, int r = n, int idx = 1) {
if (tl <= l && r <= tr) return seg[idx];
int mid = (l + r) >> 1;
int res = -1;
if (tl <= mid) res = max(res, query(tl, tr, l, mid, (idx << 1)));
if (tr > mid) res = max(res, query(tl, tr, mid + 1, r, (idx << 1) | 1));
return res;
}
set<int> s;
int totmult = 1;
int findans() {
int multi = 1;
int res = 0;
set<int>::iterator it = s.end();
while (multi <= 2e9 && it != s.begin()) {
--it;
res = (max(res, query(*it + 1, n)) * a[*it].ff) % MOD;
multi *= a[*it].ff;
}
res = (res * modinv(multi)) % MOD;
res = (res * totmult) % MOD;
return res;
}
int32_t init(int32_t N, int32_t X[], int32_t Y[]) {
n = N;
for (int i = 1; i <= n; i++) {
a[i] = {X[i - 1], Y[i - 1]};
if (a[i].ff >= 2) {
s.insert(i);
totmult = (totmult * a[i].ff) % MOD;
}
}
build();
return findans();
}
int32_t updateX(int32_t pos, int32_t val) {
pos++;
if (a[pos].ff >= 2) {
s.erase(s.find(pos));
totmult = (totmult * modinv(a[pos].ff)) % MOD;
}
a[pos].ff = val;
if (a[pos].ff >= 2) {
s.insert(pos);
totmult = (totmult * a[pos].ff) % MOD;
}
return findans();
}
int32_t updateY(int32_t pos, int32_t val) {
pos++;
a[pos].ss = val;
update(pos, val);
return findans();
}
#undef int
Compilation message
horses.cpp: In function 'long long int findans()':
horses.cpp:60:9: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
60 | while (multi <= 2e9 && it != s.begin()) {
| ^~~~~
horses.cpp: In function 'int32_t init(int32_t, int32_t*, int32_t*)':
horses.cpp:80:16: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
80 | return findans();
| ~~~~~~~^~
horses.cpp: In function 'int32_t updateX(int32_t, int32_t)':
horses.cpp:94:16: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
94 | return findans();
| ~~~~~~~^~
horses.cpp: In function 'int32_t updateY(int32_t, int32_t)':
horses.cpp:101:16: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
101 | return findans();
| ~~~~~~~^~
| # |
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 |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
319 ms |
48536 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 |
312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
