Header Ad

HackerEarth Queries problem solution

In this HackerEarth Queries problem solution, you are given an array A of N integers. Now, you are required to process queries of the following two types.
  1. pos val: Multiply val to A[pos] i.e A[pos] = A[pos] * val.  
  2. Print an integer X such that the absolute difference between the following two values (A[1] * A[2] * ...... * A[X]) and (A[X+1] * A[X+2] * ........ * A[N]) is minimized. If there are multiple such values of X, then print the smallest one.

HackerEarth Queries problem solution


HackerEarth Queries problem solution.

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll M=1e9+7;
const ld eps=1e-10;
ld inf=1e25;
ll n,m;
ll N=100002;
ld bit[100005],a[100005];

void update(ll idx, ld val){
ll x=idx;
for(;x<=n;x+=(x&-x))
bit[x]+=val;
}

ld query(ll idx){
ld ans=0;
ll x=idx;
for(;x>0;x-=(x&-x))
ans+=bit[x];
return ans;
}

ll low(ll l, ll h, ld sum)
{
ll ret=1;
while(l<=h)
{
ll mid=(l+h)>>1;
ld val=query(mid);
if(val-sum>-eps)
h=mid-1;
else
{
ret=mid;
l=mid+1;
}
}
return ret;
}

ll up(ll l, ll h, ld sum)
{
ll ret=n;
while(l<=h)
{
ll mid=(l+h)>>1;
ld val=query(mid);
if(val-sum>eps)
{
ret=mid;
h=mid-1;
}
else
l=mid+1;
}
return ret;
}

ll bin(ll l, ll h, ld sum)
{
ll ret=-1;
while(l<=h)
{
ll mid=(l+h)>>1;
ld val=query(mid);
if(fabsl(val-sum)<eps)
{
ret=mid;
h=mid-1;
}
else if(val-sum>eps)
h=mid-1;
else
l=mid+1;
}
return ret;
}

int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin>>n>>m;
ld tot=0.0;
for(ll i=1;i<=n;i++)
{
cin>>a[i];
ld val=log2(a[i]);
a[i]=val;
tot+=val;
update(i,val);
}
while(m--)
{
ll type;
cin>>type;
if(type==1)
{
ll i;
ld x;
cin>>i>>x;
ld val=log2(x);
update(i,val);
tot+=val;
a[i]+=val;
}
else
{
ld sum=tot/((ld)(2.0));
ll pos=bin(1,n,sum);
if(pos==-1)
pos=low(1,n,sum);
pos=bin(1,n,query(pos));

ld val1=query(pos);
ld val2=tot-val1;
ld ans=pos;
ld mini=fabsl(val1-val2);

for(ll j=pos-3;j<=pos+3;j++)
{
if(j>0 && j<n)
{
val1=query(j);
val2=tot-val1;
if(fabsl(val1-val2)-mini<-eps)
{
mini=fabsl(val1-val2);
ans=j;
}
}
}

pos=-1;
pos=bin(1,n,sum-0.1);
if(pos==-1)
pos=low(1,n,sum-0.1);

pos=bin(1,n,query(pos));

for(ll j=pos-3;j<=pos+3;j++)
{
if(j>0 && j<n)
{
val1=query(j);
val2=tot-val1;
if(fabsl(val1-val2)-mini<-eps)
{
mini=fabsl(val1-val2);
ans=j;
}
}
}

pos=up(1,n,sum);
val1=query(pos);
val2=tot-val1;

for(ll j=pos-3;j<=pos+3;j++)
{
if(j>0 && j<n)
{
val1=query(j);
val2=tot-val1;
if(fabsl(val1-val2)-mini<-eps)
{
mini=fabsl(val1-val2);
ans=j;
}
}
}
cout<<ans<<"\n";
}
}
return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn = 1e5 + 17;
ld fen[maxn], a[maxn];
void upd(int p, ld x){
for(p++; p < maxn; p += p & -p)
fen[p] += x;
}
ld get(int p){
ld ans = 0;
for(; p; p ^= p & -p)
ans += fen[p];
return ans;
}
int n, m;
int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
ld s = 0;
for(int i = 0; i < n; i++){
ll x;
cin >> x;
upd(i, log(x));
s += log(x);
}
while(m--){
int t;
cin >> t;
if(t == 1){
int i;
ll x;
cin >> i >> x;
i--;
upd(i, log(x));
s += log(x);
}
else{
int lo = -1, hi = n;
auto f = [&s](int i){
return abs(get(i + 1) - (s - get(i + 1)));
};
while(hi - lo > 2){
int lh = lo + (hi - lo) / 3, rh = hi - (hi - lo) / 3;
if(f(rh) >= f(lh))
hi = rh;
else
lo = lh;
}
cout << lo + 2 << '\n';
}
}
}


Post a Comment

0 Comments