HackerEarth Queries problem solution YASH PAL, 31 July 2024 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. pos val: Multiply val to A[pos] i.e A[pos] = A[pos] * val. 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. #include <bits/stdc++.h>using namespace std;#define ff first#define ss secondtypedef 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'; } }} coding problems