This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;
ll n;
vi x;
vi y;
ll mod = 1e9+7;
class OldNode{
public:
ll val = 1;
ll dn,up;
OldNode *left;
OldNode *right;
OldNode(ll _dn,ll _up,vi &init){
dn = _dn;
up = _up;
if(dn+1!=up){
left = new OldNode(dn,(dn+up)/2,init);
right = new OldNode((dn+up)/2,up,init);
val = (left->val*right->val)%mod;
} else {
val = init[dn]%mod;
}
}
ll update(ll a,ll v){
if(dn>a||up<=a) return val;
if(dn+1==up) {
return val = v%mod;
}
return val = (left->update(a,v)*right->update(a,v))%mod;
}
ll query(ll a,ll b){
if(dn>=b||up<=a) return 1;
if(a<=dn&&up<=b) return val;
return (left->query(a,b)*right->query(a,b))%mod;
}
};
pair<long double,ll> op1(pair<long double,ll> a,long double b){
return {a.first+b,a.second};
}
class Node{
public:
pair<long double,ll> val = {0,0};
long double toPush = 0;
ll dn,up;
Node *left;
Node *right;
Node(ll _dn,ll _up,vector<long double> &init){
dn = _dn;
up = _up;
if(dn+1!=up){
left = new Node(dn,(dn+up)/2,init);
right = new Node((dn+up)/2,up,init);
val = max(left->val,right->val);
} else {
val.second = dn;
val.first = init[dn];
}
}
void push(){
if(dn+1==up) return;
left->val=op1(left->val,toPush);
right->val=op1(right->val,toPush);
left->toPush+=toPush;
right->toPush+=toPush;
toPush = 0;
}
pair<long double,ll> update(ll a,ll b,long double v){
if(dn>=b||up<=a) return val;
if(a<=dn&&up<=b) {
val=op1(val,v);
toPush+=v;
return val;
}
push();
return val = max(left->update(a,b,v),right->update(a,b,v));
}
pair<long double,ll> query(ll a,ll b){
if(dn>=b||up<=a) return {-1e30,0};
if(a<=dn&&up<=b) return val;
push();
return max(left->query(a,b),right->query(a,b));
}
};
Node *st;
OldNode *stMul;
ll getAns(){
ll index = st->query(0,n).second;
ll ans = (stMul->query(0,index+1)*y[index])%mod;
//cout<<ans<<endl;
return ans;
}
int init(int N, int X[], int Y[]) {
n = N;
x.resize(n,1);
y.resize(n,1);
rep(i,0,n) x[i] = X[i];
rep(i,0,n) y[i] = Y[i];
vector<long double> stD(n);
stD[0] = log(x[0]);
rep(i,1,n) stD[i] = log(x[i]) + stD[i-1];
rep(i,0,n) stD[i] += log(y[i]);
st = new Node(0,N,stD);
stMul = new OldNode(0,N,x);
rep(i,0,n){
//updateX(i,X[i]);
//updateY(i,Y[i]);
}
/*cout<<"#######"<<endl;
rep(i,0,n) cout<<x[i]<<" ";
cout<<endl;
rep(i,0,n) cout<<y[i]<<" ";
cout<<endl;
rep(i,0,n) cout<<stMul->query(i,i+1)<<" ";
cout<<endl;
rep(i,0,n) cout<<st->query(i,i+1).first<<" ";
cout<<endl;
cout<<"#######"<<endl;*/
return getAns();
}
int updateX(int pos, int val) {
st->update(pos,n,-log((long double)(x[pos]))+log((long double)(val)));
stMul->update(pos,val);
x[pos] = val;
return getAns();
}
int updateY(int pos, int val) {
st->update(pos,pos+1,-log(y[pos])+log(val));
y[pos] = val;
return getAns();
}
Compilation message (stderr)
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:149:15: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
return getAns();
~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:156:15: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
return getAns();
~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:162:15: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
return getAns();
~~~~~~^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |