3230 - Cambridge

Enunt

Interviul de admitere la prestigioasa Universitate Cambridge constă în N probleme, numerotate de la 1 la N. Alex este în momentul acesta acolo, așteptând să susțină interviul. Takahiro Wong, care tocmai a ieșit din examen, a rezolvat toate problemele, problema i rezolvând-o după Di secunde de la începerea interviului. Cunoscând ca poate rezolva fiecare problema i în Ti secunde, Alex, panicat din fire, își pune M întrebări de forma: x y. Pentru fiecare întrebare, Alex vrea să afle dacă poate rezolva fiecare problemă din intervalul [x;y] înaintea lui Takahiro Wong (Alex poate rezolva problemele din intervalul [x;y] în ce ordine dorește). De exemplu, să considerăm că Alex rezolvă problemele a și b (în această ordine). El va termina problema a după Ta secunde, și problema b după Ta + Tb secunde. Alex va rezolva ambele probleme înaintea lui Takahiro Wong dacă Ta < Da și Ta + Tb < Db. Atât interviul lui Takahiro Wong, cât și cel al lui Alex încep de la secunda 0.

Cerinţa

Ajutați-l pe Alex să răspundă corect la cele M întrebări pentru a nu intra panicat la interviu.

Date de intrare

Pe prima linie se vor citi de la tastatura N și M, separate prin câte un spațiu. N – numărul de probleme, M – numărul de întrebări.

Pe următoarele N linii se vor citi de la tastatura Ti și Di, separate prin câte un spațiu. Ti – timpul necesar lui Alex sa rezolve problema i. Di – timpul (de la începerea interviului) după care Takahiro Wong rezolv[ problema i.

Pe următoarele M linii se vor citi de la tastatură x și y, separate prin câte un spațiu. x – capătul din stânga al intervalului. y – capătul din dreapta al intervalului.

Date de ieșire

Se vor afișa pe ecran M linii – răspunsurile la cele M întrebări. Linia cu numărul i va conține răspunsul pentru întrebarea cu numărul i: 1, dacă Alex poate găsi o ordine în care să rezolve toate problemele din intervalul [x;y], astfel încât să termine fiecare problema înaintea lui Takahiro Wong, sau 0, altfel.

Restricţii şi precizări

• 1 ≤ N, M ≤ 100.000
• 1 ≤ Ti, Di ≤ 1.000.000.000
• Valorile Di nu sunt distincte două câte două (o valoarea poate apărea de mai multe ori)
• Alex nu poate rezolva două probleme în același timp, însă Takahiro Wong poate (valorile Di nu sunt distincte două câte două).

Exemplul 1

Intrare

4 3
1 10
14 18
2 7
10 12
3 4
2 4
1 3

Ieșire

0
0
1

Explicație

Sunt 4 probleme, numerotate de la 1 la 4:

• problema numărul 1: T1 = 1, D1 = 10;
• problema numărul 2: T2 = 14, D2 = 18;
• problema numărul 3: T3 = 2, D3 = 7;
• problema numărul 4: T4 = 10, D4 = 12;
• Prima întrebare se referă la intervalul [3,4]: – Dacă rezolvăm problemele în ordinea (3,4) trebuie să avem T3 < D3 și T3 + T4 < D4. Observăm că a doua relație este falsă. – Dacă rezolvăm problemele în ordinea (4,3) trebuie să avem T4 < D4 și T4 + T3 < D3. Observăm, din nou, că a doua relație este falsă. – Nu există nicio altă ordine în care putem rezolva problemele, deci răspunsul este 0.
• A doua întrebare se referă la intervalul [2,4]: – Exista șase modalități de a rezolva problemele: (2, 3, 4), (2, 4, 3), (3, 2, 4), (3, 4, 2), (4, 2, 3), (4, 3, 2). – În niciuna din cele șase modalități nu sunt toate relațiile respectate, deci răspunsul este 0.
• A treia întrebare se referă la intervalul [1,3]: – Exista șase modalități de a rezolva problemele: (1,2,3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1). – Dacă rezolvăm problemele în ordinea (1,3,2) trebuie să avem T1 < D1, T1 + T3 < D3 și T1 + T3 + T2 < D2. * Observăm că toate sunt adevărate. – Deoarece am găsit o ordine de a rezolva problemele, pentru care toate relațiile sunt adevărate, răspunsul este 1.

Rezolvare

<syntaxhighlight lang="python" line> def can_solve_in_time_interval(N, problems, x, y):

   max_time_ending_here = 0
   for i in range(x - 1, y):
       max_time_ending_here = max(max_time_ending_here, problems[i][0]) + problems[i][1]
       if max_time_ending_here > problems[i][2]:
           return False
   return True

def main():

   N, M = map(int, input().split())

   problems = []
   for _ in range(N):
       T, D = map(int, input().split())
       problems.append((T, D, T + D))

   for _ in range(M):
       x, y = map(int, input().split())
       if can_solve_in_time_interval(N, problems, x, y):
           print(1)
       else:
           print(0)

if __name__ == "__main__":

   main()

</syntaxhighlight>