#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
vector<int> x, y;
struct SegTree {
int size = 1;
vector<long long> pr, mx;
void init(){
while(size < (int)x.size())
size <<= 1;
pr.resize(size << 1, 1);
mx.resize(size << 1, 0);
build(0, 0, size);
}
void build(int ind, int lx, int rx){
if(lx + 1 == rx){
if(lx < x.size())
pr[ind] = x[lx], mx[ind] = y[lx];
return;
}
int mid = (lx + rx) >> 1;
build((ind << 1) + 1, lx, mid);
build((ind << 1) + 2, mid, rx);
pr[ind] = (pr[(ind << 1) + 1] * pr[(ind << 1) + 2]) % mod;
mx[ind] = max(mx[(ind << 1) + 1], mx[(ind << 1) + 2]);
}
void change(int pos, int val, int x, int lx, int rx){
if(lx + 1 == rx){
pr[x] = val;
return;
}
int mid = (lx + rx) >> 1;
if(pos < mid)
change(pos, val, (x << 1) + 1, lx, mid);
else
change(pos, val, (x << 1) + 2, mid, rx);
pr[x] = (pr[(x << 1) + 1] * pr[(x << 1) + 2]) % mod;
}
void change(int pos, int val){
change(pos, val, 0, 0, size);
}
void set(int pos, int val, int x, int lx, int rx){
if(lx + 1 == rx){
mx[x] = val;
return;
}
int mid = (lx + rx) >> 1;
set(pos, val, (x << 1) + 1, lx, mid);
set(pos, val, (x << 1) + 1, mid, rx);
mx[x] = max(mx[(x << 1) + 1], mx[(x << 1) + 2]);
}
void set(int pos, int val){
set(pos, val, 0, 0, size);
}
long long get(int l, int r, int ind, int lx, int rx){
if(l <= lx and rx <= r)
return pr[ind];
if(r <= lx or rx <= l)
return 1ll;
int mid = (lx + rx) >> 1;
return (get(l, r, (ind << 1) + 1, lx, mid) * get(l, r, (ind << 1) + 2, mid, rx)) % mod;
}
long long get(int l, int r){
return get(l, r, 0, 0, size);
}
int res(int l, int r, int x, int lx, int rx){
if(l <= lx and rx <= r)
return mx[x];
if(r <= lx or rx <= l)
return 0;
int mid = (lx + rx) >> 1;
return max(res(l, r, (x << 1) + 1, lx, mid), res(l, r, (x << 1) + 2, mid, rx));
}
int res(int l, int r){
return res(l, r, 0, 0, size);
}
};
SegTree s;
set<int> st;
int init(int n, int X[], int Y[]) {
x.resize(n);
y.resize(n);
for(int i = 0; i < n; i ++)
x[i] = X[i], y[i] = Y[i];
st.insert(-1);
for(int i = 0; i < n; i ++)
if(x[i] != 1)
st.insert(i);
s.init();
long long y1 = s.res((*--st.end()) + 1, n), p = 1, ans = (s.res((*--st.end()) + 1, n) * s.get(0, *--st.end())) % mod;
auto cur = --st.end(), prev = cur;
while(1){
if(prev == st.begin())
return ans;
prev --;
p = p * x[*cur];
if(p > 1e9 or y1 * p > 1e9)
return ans;
if(s.res(*prev + 1, *cur + 1) > y1 * p){
y1 = s.res(*prev + 1, *cur + 1);
p = 1;
ans = (y1 * s.get(0, *prev + 1)) % mod;
}
cur = prev;
}
return ans;
}
int updateX(int pos, int val) {
x[pos] = val;
s.change(pos, val);
int n = (int)x.size();
long long y1 = 0, p = 1, ans = 1;
for(int i = n - 1; i >= 0; i --){
if(p > 1e9 or y1 * p > 1e9)
return ans;
if(y[i] > y1 * p){
y1 = y[i];
p = 1;
ans = (y1 * s.get(0, i + 1)) % mod;
}
p = p * x[i];
}
return ans;
}
int updateY(int pos, int val) {
y[pos] = val;
int n = (int)x.size();
long long y1 = 0, p = 1, ans = 1;
for(int i = n - 1; i >= 0; i --){
if(p > 1e9 or y1 * p > 1e9)
return ans;
if(y[i] > y1 * p){
y1 = y[i];
p = 1;
ans = (y1 * s.get(0, i + 1)) % mod;
}
p = p * x[i];
}
return ans;
}
Compilation message
horses.cpp: In member function 'void SegTree::build(int, int, int)':
horses.cpp:23:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | if(lx < x.size())
| ~~~^~~~~~~~~~
horses.cpp: In member function 'void SegTree::change(int, int, int, int, int)':
horses.cpp:34:36: warning: declaration of 'x' shadows a global declaration [-Wshadow]
34 | void change(int pos, int val, int x, int lx, int rx){
| ~~~~^
horses.cpp:6:13: note: shadowed declaration is here
6 | vector<int> x, y;
| ^
horses.cpp: In member function 'void SegTree::set(int, int, int, int, int)':
horses.cpp:51:33: warning: declaration of 'x' shadows a global declaration [-Wshadow]
51 | void set(int pos, int val, int x, int lx, int rx){
| ~~~~^
horses.cpp:6:13: note: shadowed declaration is here
6 | vector<int> x, y;
| ^
horses.cpp: In member function 'int SegTree::res(int, int, int, int, int)':
horses.cpp:79:28: warning: declaration of 'x' shadows a global declaration [-Wshadow]
79 | int res(int l, int r, int x, int lx, int rx){
| ~~~~^
horses.cpp:6:13: note: shadowed declaration is here
6 | vector<int> x, y;
| ^
horses.cpp:81:15: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
81 | return mx[x];
| ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:110:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
110 | return ans;
| ^~~
horses.cpp:113:6: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
113 | if(p > 1e9 or y1 * p > 1e9)
| ^
horses.cpp:113:20: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
113 | if(p > 1e9 or y1 * p > 1e9)
| ~~~^~~
horses.cpp:114:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
114 | return ans;
| ^~~
horses.cpp:122:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
122 | return ans;
| ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:131:6: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
131 | if(p > 1e9 or y1 * p > 1e9)
| ^
horses.cpp:131:20: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
131 | if(p > 1e9 or y1 * p > 1e9)
| ~~~^~~
horses.cpp:132:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
132 | return ans;
| ^~~
horses.cpp:140:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
140 | return ans;
| ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:148:6: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
148 | if(p > 1e9 or y1 * p > 1e9)
| ^
horses.cpp:148:20: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
148 | if(p > 1e9 or y1 * p > 1e9)
| ~~~^~~
horses.cpp:149:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
149 | return ans;
| ^~~
horses.cpp:157:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
157 | return ans;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
157 ms |
51372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
