#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
const long long MOD=1e9+7;
int n=0;
vector<int> x;
vector<int> y;
struct segtree{
vector<int> tree;
vector<int> lazy;
void init(){
tree.assign(n*4, 0);
lazy.assign(n*4, 1);
}
int MUL(int a, int b){
return (a*b)%MOD;
}
int update_node(int l, int r, int v, int val){
lazy[v] = MUL(lazy[v], val);
return tree[v] = MUL(lazy[v], val);
}
void propagate(int l, int r, int v){
if(lazy[v]==1) return;
int m=l+(r-l)/2;
update_node(l, m, v*2+1, lazy[v]);
update_node(m, r, v*2+2, lazy[v]);
lazy[v]=1;
}
int update(int l, int r, int v, int ql, int qr, int val){
if(qr<=l || r<=qr) return tree[v];
if(ql<=l && r<=qr){
return update_node(l, r, v, val);
}
propagate(l, r, v);
int m=l+(r-l)/2;
return tree[v] = MUL(update(l, m, v*2+1, ql, qr, val), update(m, r, v*2+2, ql, qr, val));
}
int query(int l, int r, int v, int ql, int qr){
if(qr<=l || r<=ql) return 1;
if(ql<=l && r<=qr){
return tree[v];
}
propagate(l, r, v);
int m=l+(r-l)/2;
return MUL(query(l, m, v*2+1, ql, qr), query(m, r, v*2+2, ql, qr));
}
};
segtree seg;
bool bigger(pair<int, long long> a, pair<int, long long> b){
return a.first*b.second > a.second*b.first;
}
int solveSlow(){
long long p=1; bool mod=false;
pair<int, long long> maxi={1, 1};
int ind=n-1;
for(int i=n-1; i>=0; i--){
if(!mod){
if(bigger({y[i], p}, maxi)){
maxi={y[i], p};
ind=i;
}
}
p*=(long long)x[i];
if(p > MOD){
p%=MOD;
mod=true;
}
}
long long ans=1;
for(int i=0; i<=ind; i++){
ans *= (long long)x[i];
ans%=MOD;
}
ans *= (long long)y[ind];
ans%=MOD;
return ans;
}
int solve3(){
long long p=1; bool mod=false;
pair<int, long long> maxi={1, 1};
int ind=n-1;
for(int i=n-1; i>=max(0, n-31); i--){
if(!mod){
if(bigger({y[i], p}, maxi)){
maxi={y[i], p};
ind=i;
}
}
p*=(long long)x[i];
if(p > MOD){
p%=MOD;
mod=true;
}
}
long long ans=seg.query(0, n, 0, 0, ind+1);
ans *= (long long)y[ind];
ans%=MOD;
return ans;
}
int solve(){
bool one=false;
for(int i=n-1; i>=max(0, n-31); i--){
if(x[i]==1) one=true;
}
if(one){
return solveSlow();
}
return solve3();
}
int init(int N, int X[], int Y[]) {
n=N;
x.assign(n, 0);
y.assign(n, 0);
for(int i=0; i<N; i++){
x[i]=X[i];
y[i]=Y[i];
}
int px=x[0];
seg.init();
seg.update(0, n, 0, 0, 1, px);
for(int i=1; i<n; i++){
px*=x[i];
px%=MOD;
seg.update(0, n, 0, i, i+1, px);
}
return solve();
}
int fastpow(int a, int b){
if(b==0) return 1;
int s=fastpow(a, b/2);
s=s*s;
s%=MOD;
if(b%2==0){
s*=a;
s%=MOD;
}
return s;
}
int inverse(int a){
return fastpow(a, MOD-2);
}
int updateX(int pos, int val) {
int change = val * inverse(x[pos]); //val/x[pos]
change%=MOD;
x[pos]=val;
seg.update(0, n, 0, pos, n, change);
return solve();
}
int updateY(int pos, int val) {
y[pos]=val;
return solve();
}
Compilation message
horses.cpp: In member function 'int segtree::update_node(int, int, int, int)':
horses.cpp:23:25: warning: unused parameter 'l' [-Wunused-parameter]
23 | int update_node(int l, int r, int v, int val){
| ~~~~^
horses.cpp:23:32: warning: unused parameter 'r' [-Wunused-parameter]
23 | int update_node(int l, int r, int v, int val){
| ~~~~^
horses.cpp: In function 'int solveSlow()':
horses.cpp:99:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
99 | return ans;
| ^~~
horses.cpp: In function 'int solve3()':
horses.cpp:132:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
132 | return ans;
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
123 ms |
23968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
