1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/* 2021
 * Maciej Szeptuch
 */
#include <algorithm>
#include <cstdio>
#include <queue>

const int MAXN = 300001;

int from[MAXN];
int queries;
int soldier[MAXN];
int soldiers;
int team;
int to[MAXN];
long long int best[MAXN];
long long int result[MAXN];
std::vector<int> ends[MAXN];
std::vector<int> starts[MAXN];
std::priority_queue<std::pair<size_t, std::pair<bool, int>>> order;

int main(void)
{
    scanf("%d %d %d", &soldiers, &team, &queries);
    for(int s = 1; s <= soldiers; ++s)
        scanf("%d", &soldier[s]);

    for(int q = 0; q < queries; ++q)
    {
        scanf("%d %d", &from[q], &to[q]);
        if(to[q] - from[q] + 1 < team)
        {
            result[q] = 1;
            continue;
        }

        starts[from[q]].push_back(q);
        ends[to[q]].push_back(q);
    }

    for(int s = 0; s < soldiers; ++s)
    {
        order.push({starts[s].size(), {1, s}});
        order.push({ends[s].size(), {0, s}});
        std::sort(std::begin(starts[s]), std::end(starts[s]), [&](auto a, auto b)
            { return to[a] == to[b] ? a < b : to[a] < to[b]; });
        std::sort(std::begin(ends[s]), std::end(ends[s]), [&](auto a, auto b)
            { return from[a] == from[b] ? a < b : from[a] < from[b]; });
    }

    while(!order.empty())
    {
        auto t = order.top();
        order.pop();

        int start = t.second.second;
        size_t q = 0;
        int direction = 0;
        std::vector<int> *queue = nullptr;
        int *target = nullptr;
        if(t.second.first)
        {
            direction = 1;
            queue = &starts[start];
            target = to;
        }
        else
        {
            direction = -1;
            queue = &ends[start];
            q = queue->size() - 1;
            target = from;
        }

        size_t e = 0;
        for(size_t p = 0; p < queue->size(); ++p)
        {
            if(!result[(*queue)[p]])
                (*queue)[e++] = (*queue)[p];
        }

        queue->resize(e);
        if(queue->size() != t.first)
        {
            order.push({queue->size(), t.second});
            continue;
        }

        best[start - direction] = 0;
        long long int current = soldier[start - direction];
        for(int s = start; q < queue->size(); s += direction)
        {
            current += soldier[s];
            if(s * direction - start * direction + 1 >= team)
            {
                current -= soldier[s - team * direction];
                best[s] = std::max(best[s - direction], best[s - team * direction] + current);
            }
            else
                best[s] = best[s - direction];

            while(q < queue->size() && target[(*queue)[q]] == s)
            {
                result[(*queue)[q]] = best[s] + 1;
                q += direction;
            }
        }
    }

    for(int q = 0; q < queries; ++q)
        printf("%lld\n", result[q] - 1);

    return 0;
}