Question

1102 PBINFO
Pe o masă cad n bile săltăreţe. Fiecare este lăsată să cadă liber de la o înălţime h, diferită pentru fiecare bilă. Toate bilele cad simultan, cu o viteză constantă (1m/s) .

În momentul în care bila i atinge masa, tendinţa ei va fi să se ridice în aer până la înălţimea h - k, după care aceasta cade din nou. De fiecare dată când o bilă atinge masa, aceasta va tinde să urce la o înlăţime cu k mai mică decât cea la care a urcat anterior. Dupa multe sărituri, bilele pot obosi şi nu vor mai sări. Când bilele sar în sus, vor urca tot cu aceeaşi viteza constantă.

Dându-se h şi k pentru fiecare dintre cele n bile, să se răspundă la m întrebări de forma: La ce înălţime faţă de masă se va afla bila x în momentul t ?

Date de intrare
Fişierul de intrare bile2.in conţine pe prima linie 2 numere naturale n şi m. Pe următoarele n linii se află o pereche de numere, h şi k . Următoarele m linii vor conţine 2 numere naturale x şi t cu semnificaţiile de mai sus.

Date de ieşire
În fişierul de ieşire bile2.out se vor afişa m linii, răspunsurile la cele m întrebări.

Restricţii
1 ≤ n, m ≤ 100.000
1 ≤ h, k ≤ 1.000.000.000
1 ≤ t ≤ 2.000.000.000
0 < x ≤ n



Exemplu
bile2.in

2 3
5 1
8 2
1 4
1 7
2 16
bile2.out

1
2
4
Explicaţie
Bila 1 cade de la înălţimea 5 timp de 4 secunde apoi se opreşte la înălţimea 1.

Bila 1 cade de la înălţimea 5 şi atinge pământul, iar în cele 2 secunde rămase ajunge la înălţimea 2.

Bila 2 cade de la înălţimea 8, atinge pământul şi apoi ajunge la noua sa înălţime maximă, 6, în 14 secunde. în cele 2 secunde rămase, bila apucă să coboare la înălţimea 4.

Answer 1

#include <fstream>  

using namespace std;  

ifstream fin("bile2.in");

ofstream fout("bile2.out");  

const int N = 1e5 + 5;  

long long h[N], k[N], n, m, x, t;  

#define max(x, y)((x) < (y) ? (y) : (x))  

int main() {

   fin >> n >> m;

   for (int i = 1; i <= n; ++i)

       fin >> h[i] >> k[i];

   for (int i = 0; i < m; ++i) {

       fin >> x >> t;

       int crt = h[x], height = h[x];

       if (t <= h[x]) {

           fout << h[x] - t << "n";

           continue;

       }

       t -= h[x];

       height = 0;

       crt -= k[x];

       while (t && crt) {

           if (t <= crt) {

               height += t;

               t = 0;

           } else {

               t -= crt;

               height = crt;

           }

           if (!t)

               break;

           if (t <= crt) {

               height -= t;

               t = 0;

           } else {

               t -= crt;

               height = 0;

           }

           crt = max(0, crt - k[x]);

       }

       fout << height << "n";

   }

}