TLE on #11 - #14

#include<bits/stdc++.h>
#define int unsigned long long
#define endl '\n'
using namespace std;
const int maxn = 2e5 + 5;
struct Nahida
{
    int l,r,val,lazy;
}tree[maxn << 2];
int n,q,w;
int cnt,ans;
int a[maxn];
int L,R,d,sum;
inline int read()
{
    int ret = 0,f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9'){f = (ch == '-' ? -1 : 1);ch = getchar();}
    while (ch >= '0' && ch <= '9'){ret = ret * 10 + ch - '0';ch = getchar();}
    return ret * f;
}
inline void push_up(int rt){tree[rt].val = tree[rt << 1].val + tree[rt << 1 | 1].val;}
inline void push_down(int rt)
{
    if(tree[rt].lazy)
    {
        tree[rt << 1].val += (tree[rt << 1].r - tree[rt << 1].l + 1) * tree[rt].lazy;
        tree[rt << 1 | 1].val += (tree[rt << 1 | 1].r - tree[rt << 1 | 1].l + 1) * tree[rt].lazy;
        tree[rt << 1].lazy += tree[rt].lazy;
        tree[rt << 1 | 1].lazy += tree[rt].lazy;
        tree[rt].lazy = 0;
    }
}
void build(int l,int r,int rt)
{
    tree[rt].l = l;
    tree[rt].r = r;
    tree[rt].lazy = 0;
    if (l == r)
    {
        tree[rt].val = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(l,mid,rt << 1);
    build(mid + 1,r,rt << 1 | 1);
    push_up(rt);
}
void upd(int ql,int qr,int val,int rt)
{
    int l = tree[rt].l;
    int r = tree[rt].r;
    if (ql <= l && r <= qr)
    {
        tree[rt].val += (tree[rt].r - tree[rt].l + 1) * val;
        tree[rt].lazy += val;
        return;
    }
    push_down(rt);
    int mid = l + r >> 1;
    if (ql <= mid)
        upd(ql,qr,val,rt << 1);
    if (qr > mid)
        upd(ql,qr,val,rt << 1 | 1);
    push_up(rt);
}
int que(int x,int rt)
{
    int l = tree[rt].l;
    int r = tree[rt].r;
    if (l == r)
        return l;
    push_down(rt);
    if (tree[rt << 1].val * (1 << cnt) >= x)
        return que(x,rt << 1);
    else
        return que(x - tree[rt << 1].val * (1 << cnt),rt << 1 | 1);
}
signed main()
{
    ios::sync_with_stdio(0);
    cout.tie(0);
    n = read(),q = read(),w = read();
    for (int i = 1; i <= n; i++)
    {
        a[i] = read();
        sum += a[i];
    }
    build(1,n,1);
    while (q--)
    {
        L = read(),R = read(),d = read();
        upd(L,R,d,1);
        sum += (R - L + 1) * d;
        cnt = 1;
        while (w > ((1 << cnt) - 1) * sum)
            cnt ++;
        cnt --;
        cout << que(w - sum * ((1 << cnt) - 1),1) + cnt * n - 1 << '\n';
    }
    return 0;
}