#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define ll long long
#define fastOI ios_base::sync_with_stdio(false); cin.tie(nullptr);
auto cmp = [](int a, int b){return a > b;};
auto cmp1 = [](pair<ll,ll> a, pair<ll,ll> b){return a.second < b.second;};
ll mod = 1000000007;
vector<ll> segtreex;
vector<ll> segtreey;
void updatex(int l, int r, int pos, int ind, ll x){
int m = l + (r - l)/2;
if(ind < l || ind >= r)return;
if(l == ind && l + 1 == r){
segtreex[pos] = x;
return;
}
updatex(l, m, pos*2, ind, x);
updatex(m, r, pos*2 + 1, ind, x);
segtreex[pos] = (segtreex[pos*2] * segtreex[pos*2 + 1])%mod;
return;
}
ll queryx(int l, int r, int pos, int ql, int qr){
if( ql >= l && qr <= r)return segtreex[pos];
if( qr <= l || ql >= r)return 1;
int m = l + (r-l)/2;
return (queryx(l, m, pos * 2, ql, qr) * queryx(m, r, pos*2 + 1, ql, qr))%mod;
}
void updatey(int l, int r, int pos, int ind, ll x){
int m = l + (r - l)/2;
if(ind < l || ind >= r)return;
if(l == ind && l + 1 == r){
segtreey[pos] = x;
return;
}
updatey(l, m, pos*2, ind, x);
updatey(m, r, pos*2 + 1, ind, x);
segtreey[pos] = max(segtreey[pos*2], segtreey[pos*2 + 1]);
return;
}
ll queryy(int l, int r, int pos, int ql, int qr){
if( ql >= l && qr <= r)return segtreey[pos];
if( qr <= l || ql >= r)return 1;
int m = l + (r-l)/2;
return max(queryy(l, m, pos * 2, ql, qr), queryy(m, r, pos*2 + 1, ql, qr));
}
set<ll> fasts;
int npo2;
vector<ll> x;
vector<ll> y;
int n;
int solve(){
if(fasts.empty()){
return queryy(0, npo2, 1, 0, npo2);
}
vector<pair<ll,ll>> solver(30,{1, 1});
set<ll>::iterator pt = fasts.end();
int opt = (min(30, int(fasts.size())));
int last = n;
ll temppro = 1;
for(int i = 0 ;i < opt; i++){
pt--;
solver[opt - i].first = x[*pt];
solver[opt - i].second = queryy(0, npo2, 1, *pt, last);
last = *pt;
temppro *= x[*pt];
if(temppro >= mod)break;
}
ll startproduct = queryx(0, npo2, 1, 0, last);
temppro = 1;
ll best = 1;
for(int i = 0; i < opt; i++){
temppro *= solver[i].first;
best = max(best, temppro * solver[i].second);
}
best %= mod;
return (best * startproduct)%mod;
//x for growth
// y for prices;
}
int init(int nn, int xx[], int yy[]){
for(int i = 0; i<n; i++){
x.push_back(xx[i]);
y.push_back(yy[i]);
}
n = nn;
npo2 = __lg(n-1) + 1;
npo2 = (1<<npo2);
segtreex.resize(npo2 * 2, 1);
segtreey.resize(npo2 * 2, 0);
for(int i = 0; i<n; i++){
if(x[i] > 1)updatex(0, npo2, 1, i, x[i]);
if(x[i] > 1)fasts.insert(i);
}
for(int i = 0; i<n; i++){
updatey(0, npo2, 1, i, y[i]);
}
return solve();
}
int updateX(int pos, int val) {
updatex(0, npo2, 1, pos, val);
if(val == 1){
fasts.erase(val);
}
else fasts.insert(val);
x[pos] = val;
return solve();
}
int updateY(int pos, int val) {
updatey(0, npo2, 1, pos, val);
y[pos] = val;
return solve();
}
Compilation message
horses.cpp: In function 'int solve()':
horses.cpp:64:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
64 | return queryy(0, npo2, 1, 0, npo2);
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~
horses.cpp:74:53: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
74 | solver[opt - i].second = queryy(0, npo2, 1, *pt, last);
| ^~~
horses.cpp:75:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
75 | last = *pt;
| ^~~
horses.cpp:87:33: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
87 | return (best * startproduct)%mod;
| ~~~~~~~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
32 ms |
41768 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
