# PBinfo #4433 – kth1 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Se dă un șir V ce conține N numere întregi numerotate începând de la 1: V[1], V[2], ..., V[N] și două numere naturale nenule K și L, cu proprietatea că: 1 ≤ K ≤ L ≤ N. Mihai studiază doar secvențele de lungime L, adică secvențele formate din exact L elemente situate pe poziții alăturate în acest șir V.

El își poate pune următoarea întrebare: “Dacă aș rearanja, în ordine crescătoare, elementele secvenței de lungime L care începe la poziția poz în șirul V, ce valoare s-ar afla pe poziția a K-a în cadrul secvenței rezultate?”. Pentru secvența din șir care începe la poziția poz și are L elemente, adică V[poz], V[poz+1], ..., V[poz+L-1], valoarea elementului de pe poziția a K-a în cadrul secvenței este V[poz+K-1].

Cerința
Ajutați-l pe Mihai să afle care este răspunsul corect pentru Q întrebări de tipul descris mai sus!

Date de intrare
Pe prima linie a fișierului de intrare kth.in se află trei numere naturale nenule N, K și L, separate între ele prin câte un spațiu, cu semnificațiile de mai sus. Pe următoarea linie se află, separate între ele prin câte un spațiu, N numere întregi, reprezentând, în ordine, elementele șirului V. Pe următoarea linie se află numărul natural nenul Q, reprezentând numărul de întrebări formulate de către Mihai. Pe fiecare dintre următoarele Q linii se află câte un număr natural nenul poz, reprezentând poziția de început a secvenței de L elemente pentru care se pune întrebarea respectivă.

Date de ieșire
Fișierul de ieșire kth.out va conține Q linii. Pe linia i se va afla un număr întreg ce reprezintă răspunsul la întrebarea i, în ordinea dată în fișierul de intrare, pentru fiecare i: 1 ≤ i ≤ Q.

Restricții și precizări

2 ≤ N ≤ 300.000 și 1 ≤ Q ≤ 300.000.
−50 000 ≤ V[i] ≤ 50.000, pentru fiecare i: 1 ≤ i ≤ N.
1 ≤ poz ≤ N − L + 1, pentru fiecare dintre cele Q întrebări.
Valorile poz din cadrul celor Q întrebări nu sunt neapărat distincte între ele oricare două.
Datorită dimensiunilor, nu toate testele au putut fi adăugate.

Exemplul 1:
kth.in

5 2 3
4 -5 2 1 4
2
2
1
kth.out

1
2
Explicație
Sunt N = 5 elemente în șirul V = (4, -5, 2, 1, 4). Pentru prima întrebare (pentru care poz = 2), dacă secvența formată din L=3 elemente: (V[2], V[3], V[4]) ar fi ordonată crescător, aceasta ar deveni: (-5, 1, 2), ceea ce înseamnă că pe cea de a doua (K = 2) poziție în cadrul ei s-ar afla valoarea 1.

Exemplul 2:
kth.in

5 2 3
1 5 2 4 3
2
2
1
kth.out

4
2
Explicație
Sunt N = 5 elemente în șirul V = (1, 5, 2, 4, 3), K = 2 și L = 3. Q = 2 întrebări formulate.

## Cod sursă C++

```cpp
/*
    Autor: stud. Andrei Onut - Universitatea Yale, S.U.A.
    Problema: Kth
*/
#include <fstream>
using namespace std;
ifstream f("kth.in");
ofstream g("kth.out");
const int NMAX = 3e5 + 1;
const int absVMAX = 5e4;
const int ADD = absVMAX + 1;
const int DIM = 317;
int N, K, L;
int V[NMAX], Max = (int)(-1e5);
int ans[NMAX];
int fr[((absVMAX << 1) + 10)];
int M, cnt_bucket[(DIM + 5)];
int my_max(int a, int b)
{
    return ((a > b) ? a : b);
}
void Read()
{
    f >> N >> K >> L;
    for (int i = 1; i <= N; ++i)
        f >> V[i], V[i] += ADD, Max = my_max(Max, V[i]);
    return;
}
int Find(int pos)
{
    return (int)((pos + DIM - 1) / DIM);
}
void Modify(int X, int Val)
{
    fr[X] += Val;
    cnt_bucket[(int)(Find(X))] += Val;
    return;
}
int Find_Kth()
{
    int sum = 0;
    int ans = 0;
    for (int i = 1; i <= M; ++i)
    {
        sum += cnt_bucket[i];
        if (sum >= K)
        {
            int sum_prime = sum - cnt_bucket[i];
            int need = K - sum_prime;
            int left = ((i - 1) * DIM + 1), right = (i * DIM);
            for (int x = left; x <= right; ++x)
                if (fr[x] > 0)
                {
                    need -= fr[x];
                    if (need <= 0)
                    {
                        ans = x;
                        break;
                    }
                }
            break;
        }
    }
    return ans;
}
void Load()
{
    for (int i = 1; i <= L; ++i)
        Modify(V[i], +1);
    ans[1] = Find_Kth();
    return;
}
void Precalculation()
{
    M = Find(Max);
    Load();
    for (int i = 2; i <= (N - L + 1); ++i)
    {
        Modify(V[i - 1], -1);
        Modify(V[(i + L - 1)], +1);
        ans[i] = Find_Kth();
    }
    for (int i = 1; i <= (N - L + 1); ++i)
        ans[i] -= ADD;
    return;
}
void Test_Case()
{
    int pos = 0;
    f >> pos;
    g << ans[pos] << '\n';
    return;
}
void Solve()
{
    int Q = 0;
    f >> Q;
    for (int q = 1; q <= Q; ++q)
        Test_Case();
    return;
}
int main()
{
    Read();
    Precalculation();
    Solve();
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4433)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4433/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4433/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)