RoAlgo Contest #7 | joingraf

This was the problem page during the contest. Access the current page here.
Time limit: 0.5s
Memory limit: 64MB
Input:
Output:

"Câinii vorbesc."

A fost ziua lui Traian de curând, iar el a primit în dar un graf cu NN noduri. La început, fiecare nod era într-o componentă conexă, singur. Dar apoi, câinele lui Traian a venit și i-a spus QQ întrebări de forma următoare:

  • 1 x y1 \ x \ y: Adaugă la graful tău muchiile (x,x+1),(x+1,x+2),...,(y1,y)(x, x + 1), (x + 1, x + 2), ..., (y - 1, y)
  • 2 x y2 \ x \ y: Spune dacă nodurile xx și yy sunt în aceeași componentă conexă.

Cerință

Răspunde la întrebările câinelui lui Traian.

Date de intrare

Pe prima linie se vor afla NN și QQ, reprezentând numărul de noduri ale grafului, respectiv numărul de întrebări. Pe următoarele QQ linii se află trei numere ti,xi,yit_i, x_i, y_i, unde tit_i reprezintă tipul întrebării , iar xix_i și yiy_i 2 noduri din graf.

Date de ieșire

Pe linia ii se va afla răspunsul la a ii-a întrebare de tip 22. Acest răspuns poate fi doar de forma Da sau Nu, depinzând de răspuns.

Restricții și precizări

  • 1N,Q1061 \leq N, Q \leq 10^6
  • Dacă la o întrebare de tip 11, o muchie a fost deja adăugată, Traian nu o va mai adăuga.
  • Pentru întrebări de tip 22, nu este garantat că xyx \leq y
# Scor Restricții
1 10 N100,Q100N \leq 100, Q \leq 100
2 10 N1 000,Q100N \leq 1 \ 000, Q \leq 100
3 10 N104,Q104N \leq 10^4, Q \leq 10^4
4 20 N105,Q105N \leq 10^5, Q \leq 10^5
5 50 Fără restricții suplimentare

Exemplu

stdin

7 6
1 4 7
2 5 3
1 3 6
1 6 7
2 7 1
2 3 4

stdout

Nu
Nu
Da

Explicație

După întrebarea 11, graful va arăta astfel:

Răspunsul la întrebarea 22 este nu, deoarece 33 și 55 nu sunt în aceeași componentă conexă.
După întrebarea 33, graful va arăta astfel:

După întrebarea 44, graful va arăta astfel:

Răspunsul la întrebarea 55 este nu, deoarece 11 și 77 nu sunt în aceeași componentă conexă.
Răspunsul la întrebarea 66 este da, deoarece 33 și 55 sunt în aceeași componentă conexă.

Contest info

Official contest

Start time: 1699171200000

Total duration: 4h0m0s

Status: Ended

Log in or sign up to be able to send submissions!