#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define REP(i,l,r) for(long long i=(l);i<(r);i++)
#define PER(i,l,r) for(long long i=(r)-1;i>=(l);i--)
const long long mod=1e9+7;
long long p(long long x){while(x&(x-1)){x=x&(x-1);}return x;}
long long squared(long long x){return (x*x)%mod;}
long long power(long long x,long long p){if(p==0){return 1;}if(p%2==1){return (power(x,p-1)*x)%mod;}return squared(power(x,p/2));}
long long inv(long long x){return power(x,mod-2);}
struct segment_tree
{
struct node
{
long double value;
long pos,left,right;
};
node dum;
vector<node>tree;
vector<long double>upd;
node operation(node x,node z)
{
node ret;
if(x.value>=z.value){
ret.value=x.value;
ret.pos=x.pos;
}
else{
ret.value=z.value;
ret.pos=z.pos;
}
ret.left=min(x.left,z.left);
ret.right=max(x.right,z.right);
return ret;
}
void push(long node)
{
tree[node].value+=upd[node];
if(node<tree.size()){
upd[node*2]+=upd[node];
upd[(node*2)+1]+=upd[node];
}
upd[node]=0;
}
void build(vector<long double>v)
{
tree.clear();
upd.clear();
int x=((v.size())*2)-1;
while(x&(x-1)){
x=x&(x-1);
}
tree.resize(x*2);
upd.resize(x*2);
dum.value=-1e9;
dum.left=-1e9;
dum.right=1e9;
for(long i=0;i<(long)v.size();i++){
tree[i+x].value=v[i];
tree[i+x].pos=i;
tree[i+x].left=i;
tree[i+x].right=i;
}
for(long i=(long)v.size();i<x;i++){
tree[i+x].value=-1e9;
tree[i+x].pos=i;
tree[i+x].left=i;
tree[i+x].right=i;
}
for(long i=x-1;i>0;i--){
tree[i]=operation(tree[i*2],tree[(i*2)+1]);
}
}
node get(int l,int r,int node=1)
{
push(node);
if(tree[node].left>r||tree[node].right<l){
return dum;
}
if(tree[node].left>=l&&tree[node].right<=r){
return tree[node];
}
return operation(get(l,r,node*2),get(l,r,(node*2)+1));
}
void update(int l,int r,long double z,int node=1)
{
push(node);
if(tree[node].left>r||tree[node].right<l){
return;
}
if(tree[node].left>=l&&tree[node].right<=r){
upd[node]+=z;
push(node);
return;
}
update(l,r,z,node*2);
update(l,r,z,(node*2)+1);
tree[node]=operation(tree[node*2],tree[(node*2)+1]);
}
};
struct segment_tree_mul
{
struct node
{
long long value,left,right;
};
node dumm;
vector<node>treee;
vector<long long>updd;
node operation(node x,node z)
{
node ret;
ret.value=max(x.value,z.value);
ret.left=min(x.left,z.left);
ret.right=max(x.right,z.right);
return ret;
}
void pushh(long node)
{
if(updd[node]!=1){
treee[node].value*=updd[node];
treee[node].value%=mod;
if(node<treee[0].value){
updd[node*2]*=updd[node];
updd[node*2]%=mod;
updd[(node*2)+1]*=updd[node];
updd[(node*2)+1]%=mod;
}
updd[node]=1;
}
}
void build(vector<long long>v)
{
treee.clear();
updd.clear();
long long x=((v.size())*2)-1;
while(x&(x-1)){
x=x&(x-1);
}
treee.resize(x*2);
updd.resize(x*2);
treee[0].value=x;
dumm.value=1;
dumm.left=-1e18;
dumm.right=1e18;
for(long i=0;i<(long)v.size();i++){
updd[i+x]=1;
treee[i+x].value=v[i];
treee[i+x].left=i;
treee[i+x].right=i;
}
for(long i=(long)v.size();i<x;i++){
updd[i+x]=1;
treee[i+x].value=1;
treee[i+x].left=i;
treee[i+x].right=i;
}
for(long i=x-1;i>0;i--){
updd[i]=1;
treee[i]=operation(treee[i*2],treee[(i*2)+1]);
}
}
node gett(long long l,long long r,long node=1)
{
pushh(node);
if(treee[node].left>r||treee[node].right<l){
return dumm;
}
if(treee[node].left>=l&&treee[node].right<=r){
return treee[node];
}
return operation(gett(l,r,node*2),gett(l,r,(node*2)+1));
}
void updatee(long long l,long long r,long long z,long long node=1)
{
pushh(node);
if(treee[node].left>r||treee[node].right<l){
return;
}
if(treee[node].left>=l&&treee[node].right<=r){
updd[node]*=z;
updd[node]%=mod;
pushh(node);
return;
}
updatee(l,r,z,node*2);
updatee(l,r,z,(node*2)+1);
treee[node]=operation(treee[node*2],treee[(node*2)+1]);
}
};
segment_tree st;
segment_tree_mul ans;
long n;
vector<long long>x,y,total;
vector<long double>v;
int init(int N, int X[], int Y[]) {
n=N;
x.resize(n);
y.resize(n);
total.resize(n);
v.resize(n);
REP(i,0,n){
x[i]=X[i];
y[i]=Y[i];
}
v[0]=log(x[0])+log(y[0]);
total[0]=x[0];
REP(i,1,n){
v[i]=v[i-1]+log(x[i])+log(y[i])-log(y[i-1]);
total[i]=(total[i-1]*x[i])%mod;
}
st.build(v);
ans.build(total);
N=st.get(0,n-1).pos;
return (total[N]*y[N])%mod;
}
int updateX(int pos, int val) {
long long V=val;
st.update(pos,n-1,log(V)-log(x[pos]));
ans.updatee(pos,n-1,(V*inv(x[pos]))%mod);
x[pos]=V;
V=st.get(0,n-1).pos;
return (ans.gett(V,V).value*y[V])%mod;
}
int updateY(int pos, int val) {
long long V=val;
st.update(pos,pos,log(V)-log(y[pos]));
y[pos]=V;
V=st.get(0,n-1).pos;
return (ans.gett(V,V).value*y[V])%mod;
}
Compilation message
horses.cpp: In member function 'void segment_tree::push(long int)':
horses.cpp:37:20: warning: declaration of 'node' shadows a member of 'segment_tree' [-Wshadow]
37 | void push(long node)
| ~~~~~^~~~
horses.cpp:14:12: note: shadowed declaration is here
14 | struct node
| ^~~~
horses.cpp:40:16: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<segment_tree::node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | if(node<tree.size()){
| ~~~~^~~~~~~~~~~~
horses.cpp: In member function 'void segment_tree::build(std::vector<long double>)':
horses.cpp:50:29: warning: conversion from 'std::vector<long double>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
50 | int x=((v.size())*2)-1;
| ~~~~~~~~~~~~~~^~
horses.cpp: In member function 'segment_tree::node segment_tree::get(int, int, int)':
horses.cpp:75:30: warning: declaration of 'node' shadows a member of 'segment_tree' [-Wshadow]
75 | node get(int l,int r,int node=1)
| ~~~~^~~~~~
horses.cpp:14:12: note: shadowed declaration is here
14 | struct node
| ^~~~
horses.cpp: In member function 'void segment_tree::update(int, int, long double, int)':
horses.cpp:86:47: warning: declaration of 'node' shadows a member of 'segment_tree' [-Wshadow]
86 | void update(int l,int r,long double z,int node=1)
| ~~~~^~~~~~
horses.cpp:14:12: note: shadowed declaration is here
14 | struct node
| ^~~~
horses.cpp: In member function 'void segment_tree_mul::pushh(long int)':
horses.cpp:119:21: warning: declaration of 'node' shadows a member of 'segment_tree_mul' [-Wshadow]
119 | void pushh(long node)
| ~~~~~^~~~
horses.cpp:104:12: note: shadowed declaration is here
104 | struct node
| ^~~~
horses.cpp: In member function 'segment_tree_mul::node segment_tree_mul::gett(long long int, long long int, long int)':
horses.cpp:164:44: warning: declaration of 'node' shadows a member of 'segment_tree_mul' [-Wshadow]
164 | node gett(long long l,long long r,long node=1)
| ~~~~~^~~~~~
horses.cpp:104:12: note: shadowed declaration is here
104 | struct node
| ^~~~
horses.cpp: In member function 'void segment_tree_mul::updatee(long long int, long long int, long long int, long long int)':
horses.cpp:175:64: warning: declaration of 'node' shadows a member of 'segment_tree_mul' [-Wshadow]
175 | void updatee(long long l,long long r,long long z,long long node=1)
| ~~~~~~~~~~^~~~~~
horses.cpp:104:12: note: shadowed declaration is here
104 | struct node
| ^~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:215:17: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
215 | N=st.get(0,n-1).pos;
| ~^~
horses.cpp:215:21: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
215 | N=st.get(0,n-1).pos;
| ~~~~~~~~~~~~~~^~~
horses.cpp:216:27: 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]
216 | return (total[N]*y[N])%mod;
| ~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:221:17: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
221 | st.update(pos,n-1,log(V)-log(x[pos]));
| ~^~
horses.cpp:224:17: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
224 | V=st.get(0,n-1).pos;
| ~^~
horses.cpp:225:38: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
225 | return (ans.gett(V,V).value*y[V])%mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:232:17: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
232 | V=st.get(0,n-1).pos;
| ~^~
horses.cpp:233:38: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
233 | return (ans.gett(V,V).value*y[V])%mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
280 ms |
127468 KB |
Output is correct |
| 2 |
Incorrect |
427 ms |
127504 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
428 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
