#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
typedef long double ld;
#define fi first
#define se second
ll mod = 1e9 + 7;
vector<pair<ll, ld>> st;
vector<pair<ll, ld>> lz;
vector<ll> x;
vector<ll> y;
int n;
int len = 1;
ll pow(ll n, ll k){
n %= mod;
ll res = 1;
while(k > 0){
if(k % 2) res = res * n % mod;
k /= 2;
n = n * n % mod;
}
return res;
}
ll modInv(ll x){
return pow(x, mod - 2);
}
void prop(int i){
st[i * 2].fi = st[i * 2].fi * lz[i].fi % mod;
st[i * 2].se += lz[i].se;
lz[i * 2].fi = lz[i * 2].fi * lz[i].fi % mod;
lz[i * 2].se += lz[i].se;
st[i * 2 + 1].fi = st[i * 2 + 1].fi * lz[i].fi % mod;
st[i * 2 + 1].se += lz[i].se;
lz[i * 2 + 1].fi = lz[i * 2 + 1].fi * lz[i].fi % mod;
lz[i * 2 + 1].se += lz[i].se;
}
void upd(int l, int r, ll mval, ld lval, int i = 1, int s = 0, int e = len){
if(l >= e || s >= r) return;
if(l <= s && e <= r){
st[i].fi = st[i].fi * mval % mod;
st[i].se += lval;
lz[i].fi = lz[i].fi * mval % mod;
lz[i].se += lval;
return;
}
prop(i);
upd(l, r, mval, lval, i * 2, s, (s + e) / 2);
upd(l, r, mval, lval, i * 2 + 1, (s + e) / 2, e);
if(st[i * 2].second > st[i * 2 + 1].second){
st[i] = st[i * 2];
}
else st[i] = st[i * 2 + 1];
}
int init(int N, int X[], int Y[]) {
x.assign(X, X + N);
y.assign(Y, Y + N);
n = N;
while(len < N) len *= 2;
st.resize(2 * len, {1, 0});
lz.resize(2 * len, {1, 0});
for (int i = 0; i < N; i++) {
st[len + i].fi = st[len + i - 1].fi * x[i] % mod;
st[len + i].second = st[len + i - 1].se + logl(x[i]);
}
for (int i = 0; i < N; i++) {
st[len + i].fi = st[len + i].fi * y[i] % mod;
st[len + i].se += logl(y[i]);
}
for (int i = len - 1; i > 0; i--) {
if(st[i * 2].second > st[i * 2 + 1].second){
st[i] = st[i * 2];
}
else st[i] = st[i * 2 + 1];
}
return st[1].first;
}
int updateX(int pos, int val) {
upd(pos, len + 1, val * modInv(x[pos]) % mod, logl(val) - logl(x[pos]));
x[pos] = val;
return st[1].first;
}
int updateY(int pos, int val) {
upd(pos, pos + 1, val * modInv(y[pos]) % mod, logl(val) - logl(y[pos]));
y[pos] = val;
return st[1].first;
}
Compilation message
horses.cpp: In function 'll pow(ll, ll)':
horses.cpp:19:11: warning: declaration of 'n' shadows a global declaration [-Wshadow]
19 | ll pow(ll n, ll k){
| ~~~^
horses.cpp:16:5: note: shadowed declaration is here
16 | int n;
| ^
horses.cpp: In function 'll modInv(ll)':
horses.cpp:30:14: warning: declaration of 'x' shadows a global declaration [-Wshadow]
30 | ll modInv(ll x){
| ~~~^
horses.cpp:14:12: note: shadowed declaration is here
14 | vector<ll> x;
| ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:89:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
89 | return st[1].first;
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:96:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
96 | return st[1].first;
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:103:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
103 | return st[1].first;
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
600 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
344 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
344 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
0 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
0 ms |
436 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Correct |
0 ms |
344 KB |
Output is correct |
| 20 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
400 KB |
Output is correct |
| 7 |
Correct |
0 ms |
436 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
344 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
432 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
0 ms |
348 KB |
Output is correct |
| 17 |
Correct |
0 ms |
348 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Correct |
1 ms |
348 KB |
Output is correct |
| 20 |
Correct |
1 ms |
348 KB |
Output is correct |
| 21 |
Correct |
1 ms |
348 KB |
Output is correct |
| 22 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 23 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
210 ms |
82428 KB |
Output is correct |
| 2 |
Incorrect |
275 ms |
91316 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
344 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
344 KB |
Output is correct |
| 13 |
Correct |
1 ms |
344 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
0 ms |
348 KB |
Output is correct |
| 16 |
Correct |
0 ms |
436 KB |
Output is correct |
| 17 |
Correct |
0 ms |
348 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Correct |
1 ms |
348 KB |
Output is correct |
| 20 |
Correct |
0 ms |
348 KB |
Output is correct |
| 21 |
Correct |
0 ms |
348 KB |
Output is correct |
| 22 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 23 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
344 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
0 ms |
432 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Correct |
0 ms |
348 KB |
Output is correct |
| 20 |
Correct |
0 ms |
344 KB |
Output is correct |
| 21 |
Correct |
1 ms |
344 KB |
Output is correct |
| 22 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 23 |
Halted |
0 ms |
0 KB |
- |
