book.cpp

#include <iostream>
#include <vector>
using namespace std;

vector<int> V, P;
int a, b;

void Input()
{
    char A[500001];
    cin.getline(A, 500001);
    int i = 0, j = 0;
    while (A[i])
    {
        if (A[i] == ' ')
        {
            V.push_back(j);
            j = 0;
        }
        else ++j;
        ++i;
    }
    V.push_back(j);
    cin >> a >> b;
}

void Precomute()
{
    P.resize(V.size());
    P[0] = V[0];
    for (int i = 1; i < V.size(); ++i)
        P[i] = P[i - 1] + V[i];
}

int beg, lim, lim2;
int FindMax(int low, int high, int max)
{
    if (low > high) return max;
    int mid = (low + high) / 2;
    int val = P[mid] + mid - beg;
    if (val > lim + lim2) return FindMax(low, mid - 1, max);
    if (mid > max) max = mid;
    return FindMax(mid + 1, high, max);
}

int Compute(int k)
{
    beg = 0; lim = k; lim2 = 0;
    int ret = 0;
    while (beg < P.size())
    {
        int max = FindMax(beg, P.size() - 1, 0);
        lim2 = P[max];
        ret += V[beg] + 1;
        beg = max + 1;
    }
    return ret - 1;
}

int main()
{
    Input();
    Precomute();
    for (int i = a; i <= b; ++i)
        cout << Compute(i) << '\n';
}