# PBinfo #3394 – mere1 – Rezolvare C++

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

## Enunț

În grădina lui Cosmin se află un măr cu număr nelimitat de mere. Cei N prieteni ai lui Cosmin, numerotați de la 1 la N, vor culege mere timp de T zile, după următoarea regulă:
În dimineața zilei Ti, prietenii lui Cosmin vor forma o coadă la intrarea în grădina, începând cu prietenul Xi. Așadar, coada va arăta sub forma Xi, Xi+1, …, XN, X1, …, Xi-1. În acea zi se vor culege Yi mere. Fiecare prieten Xi va intra în grădină, va culege un măr și se va întoarce în coadă. 
În ziua T + 1, Cosmin alege aleatoriu K prieteni (Q1, …, Qk) și dorește să afle câte mere a cules fiecare.

Cerința
Scrieţi un program care să găsească numărul de mere culese de fiecare dintre cei K prieteni selectați de Cosmin.

Date de intrare
Fișierul de intrare mere.in conține:
- Pe prima linie, N T K, trei numere întregi reprezentând numărul de prieteni, numărul de zile în care se vor culege mere și numărul de întrebări ale lui Cosmin.
- Pe următoarele T linii, câte două numere întregi, separate printr-un spațiu, Xi și Yi, reprezentând indicele prietenul ce va intra primul în grădina, respectiv numărul de mere ce vor fi culese în ziua Ti.
- Pe ultima linie, K numere întregi, Qi, reprezentând indicii prietenilor lui Cosmin, pentru care se dorește aflarea numărului de mere culese.

Date de ieșire
Fișierul de ieșire mere.out va conţine K numere întregi, pe o singură linie, separate printr-un spațiu, reprezentând răspunsurile la cele K întrebări.

Restricții și precizări

1 ≤ Xi ≤ N ≤ 10.000.000
1 ≤ T ≤ 200.000
1 ≤ K ≤ 100.000
1 ≤ Yi ≤ 1.000.000
Pentru teste în valoare de 30 puncte: 1 ≤ Xi ≤ N ≤ 100, 1 ≤ T ≤ 100, 1 ≤ K ≤ 100, 1 ≤ Yi ≤ 1.000
Pentru teste în valoare de 50 puncte:  1 ≤ Xi ≤ N ≤ 200.000, 1 ≤ T ≤ 10.000, 1 ≤ K ≤ 10.000
Pentru teste în valoare de 70 puncte:  1 ≤ Xi ≤ N ≤ 1.000.000, 1 ≤ T ≤ 100.000

Exemplu:
mere.in

5 3 4
1 2
3 5
2 7
2 4 1 2
mere.out

4 2 3 4
Explicație
5 persoane vor culege mere timp de 3 zile, astfel:
În prima zi, vor culege 2 mere persoanele cu indicii 1 și 2
În a doua zi, vor culege 5 mere persoanele cu indicii 3, 4, 5, 1 și 2
În a treia zi, vor culege 7 mere persoanele cu indicii 2, 3, 4, 5, 1, 2, 3.
Așadar, numărul de mere culese de fiecare persoană de la 1 la N este: 1 -> 3, 2 -> 4, 3 -> 3, 4 -> 2, 5 -> 2.

## Cod sursă C++

```cpp
//Sursa: Cosmin-Dumitru Oprea
#include <cstdio>
#include <algorithm>
#include <vector>
#define TMax 200000
#define KMax 100000
long long ans;
int vx[TMax+1], vy[TMax+1], n, t, k;
struct Elem {
    int pos;
    int x;
    long long val;
} Q[KMax+1];
bool cmp_pos(const Elem &A, const Elem &B)
{
    return A.pos < B.pos;
}
bool cmp_x(const Elem &A, const Elem &B)
{
    return A.x < B.x;
}
struct comparer
{
    bool operator ()(Elem const& p, int const i) const
    {
        return p.x < i;
    }
};
inline void add(int poz, int val)
{
    if (poz == 0)
        poz = n;
    std::lower_bound(Q + 1, Q + k + 1, poz, comparer())->val += val;
}
void read()
{
    scanf("%d %d %d", &n, &t, &k);
    for (int i = 1; i <= t; ++i) {
        scanf("%d %d", vx + i, vy + i);
    }
    for (int i = 1; i <= k; ++i){
        scanf("%d", &Q[i].x);
        Q[i].pos = i;
		Q[i].val = 0;
    }
}
void build_solution()
{
    std::sort(Q + 1, Q + k + 1, cmp_x);
    for (int i = 1; i <= t; ++i) {
        int x = vx[i];
        int y = vy[i];
        if (y >= n) {
            ans += 1LL * y / n;
            y = y % n;
        }
		if (y == 0) {
			continue;
		}
        add(x, 1);
        if (x + y - 1 <= n)
        {
            add(x + y, -1);
        }
        else
        {
            add(1, 1);
            add(x + y - n, -1);
        }
    }
    for (int i = 1; i <= k; ++i) {
        Q[i].val += Q[i - 1].val;
    }
}
void print_solution()
{
    std::sort(Q + 1, Q + k + 1, cmp_pos);
    for (int i = 1; i <= k; ++i) {
        printf("%lld ", ans + Q[i].val);
    }
}
int main()
{
    freopen("mere.in", "r", stdin);
    freopen("mere.out", "w", stdout);
    read();
    build_solution();
    print_solution();
    return 0;
}
```

## Resurse

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