guloso _ contestbruno

/**
 * N = tamanho do vetor arr
 * In this code we have a very large array called arr, and very large set of operations
 * Build tree: build_tree(1, 0, N-1)  // padrão
 * Update tree: update_tree(1, 0, N-1, i, j, value) (i,j) intervalo de (0, N-1) (value) valor a ser somado/setado/etc
 * Query tree: query_tree(1, 0, N-1, i, j)  (i,j) intervalo (0, N-1)
 * (1, 0, N-1) das 3 funções, padrão.
 */

#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <stdio.h>

#define NMAX 1000009 // tamanho max do vetor(arr)
#define inf 0x7fffffff
#define MAX 5100000 // tamanho da Arvore(tree) (int)(2 * pow(2.0, floor((log((double)N) / log(2.0)) + 1)));

typedef long long ll;

using namespace std;

int arr[NMAX];  // armazena os valores da entrada
int tree[MAX];
ll N;

void build_tree(int node, int a, int b) {

    if(a > b) return; // fora do intervalo

    if(a == b) { // nó folha
        tree[node] = arr[a]; // Init value
        return;
    }

    int left = node*2, right = node*2+1, mid = (a+b)/2;

    build_tree(left, a, mid); // Init left child
    build_tree(right, 1+mid, b); // Init right child

    tree[node] = max(tree[left], tree[right]); // Init root value exemplo min
   // tree[node] = tree[left] * tree[right]; /// MODIFICA AQUI(max,min,soma,mult,etc);
}


void update_tree(int node, int a, int b, int i, int j, int value) {

    if(a > b || a > j || b < i) // Current segment is not within range [i, j]
        return;

    if(a == b) { // Nó folha
            tree[node] = value;  // Aqui é onde acontece o update MODIFICAR!!
            return;               // tree[node] += value;   etc
    }

    int left = node*2, right = node*2+1, mid = (a+b)/2;

    update_tree(left, a, mid, i, j, value); // Updating left child
    update_tree(right, 1+mid, b, i, j, value); // Updating right child

    tree[node] = max(tree[node*2], tree[node*2+1]); // Updating root with min value
   // tree[node] = tree[left] * tree[right];  // MODIFICA AQUI(max,min,soma,mult,etc);
}


int query_tree(int node, int a, int b, int i, int j) {

    if(a > b || a > j || b < i) return -inf; // Out of range

    if(a >= i && b <= j) // Current segment is totally within range [i, j]
        return tree[node];

    int left = node*2, right = node*2+1, mid = (a+b)/2;

    int q1 = query_tree(left, a, mid, i, j); // Query left child
    int q2 = query_tree(right, 1+mid, b, i, j); // Query right child

    if(q1 == -inf) return q2;
    if(q2 == -inf) return q1;

    int res = max(q1, q2); // Return final result
    //int res = q1 * q2;  // MODIFICA AQUI(max,min,soma,mult,etc)

    return res;
}

int main() {

        ll t, s, k;

        scanf("%lld",&t);

        while(t--){

            scanf("%lld%lld%lld",&N,&k,&s);
            arr[0] = s;

            for (int i = 1; i < N; ++i)
                 arr[i] = (1LL*arr[i-1]*1103515245 + 12345) % (2147483648LL);

            build_tree(1, 0, N-1);  // constói a arvore

            ll ans, soma = 0;

            int fim = N-k+1;

            for(int i=0; i<fim; i++){
                 ll ans = query_tree(1, 0, N-1, i, i+k-1);
                 soma += ans;
            }

            printf("%lld\n",soma);

        }

        return 0;
}