三分

CF1933E Turtle vs. Rabbit Race: Optimal Trainings

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;
typedef long long LL;

int a[N], s[N];
int n, q;

LL check(int u, int l, int r)
{
    int k = s[r] - s[l - 1];
    return 1ll * u * k - 1ll * (k - 1) * k / 2;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T --)
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; i ++)
        {
            scanf("%d", &a[i]);
            s[i] = s[i - 1] + a[i];
        }
        scanf("%d", &q);
        while (q --)
        {
            int l, u;
            scanf("%d%d", &l, &u);
            int ll = l, rr = n;
            while (ll < rr)
            {
                int mid = ll + rr >> 1;
                int mmid = mid + 1;
                if (check(u, l, mid) < check(u, l, mmid)) ll = mid + 1;
                else    rr = mmid - 1;
            }
            printf("%d ", ll);
        }
        puts("");
    }

    return 0;
}