1102 - Bile 2

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 input.txt 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 output.txt se vor afişa m linii, răspunsurile la cele m întrebări.

Restricţii

• 1 ≤ n, m ≤ 100.000

Exemplul 1

input.txt:

2 3

5 1

8 2

1 4

1 7

2 16

output.txt:

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.

Exemplul 2

input.txt:

999999999999 3

5 1

8 2

1 4

1 7

2 16

Output:

Constraints not met!

Rezolvare

def verify_constraints(n, m):
    return 1 <= n <= 100000 and 1 <= m <= 100000

def main():
    with open("input.txt", "r") as fin, open("output.txt", "w") as fout:
        N = 100005
        h = [0] * N
        k = [0] * N

        n, m = map(int, fin.readline().split())

        if not verify_constraints(n, m):
            print("Constraints not met!")
            return

        for i in range(1, n + 1):
            h[i], k[i] = map(int, fin.readline().split())

        for _ in range(m):
            x, t = map(int, fin.readline().split())

            crt = h[x]
            height = h[x]

            if t <= h[x]:
                fout.write(f"{h[x] - t}\n")
                continue

            t -= h[x]
            height = 0
            crt -= k[x]

            while t and crt:
                if t <= crt:
                    height += t
                    t = 0
                else:
                    t -= crt
                    height = crt

                if not t:
                    break

                if t <= crt:
                    height -= t
                    t = 0
                else:
                    t -= crt
                    height = 0

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

            fout.write(f"{height}\n")

if __name__ == "__main__":
    main()