Ping-Pong (Easy Version) (Codeforces 320B)
Tags: Others, graphs

In this problem at each moment you have a set of intervals. You can move from interval (a, b) from our set to interval (c, d) from our set if and only if c < a < d or c < b < d. Also there is a path from interval I1 from our set to interval I2 from our set if there is a sequence of successive moves starting from I1 so that we can reach I2.Your program should handle the queries of the following two types:  "1 x y" (x < y) — add the new interval (x, y) to the set of intervals. The length of the new interval is guaranteed to be strictly greater than all the previous intervals. "2 a b" (a ≠ b) — answer the question: is there a path from a-th (one-based) added interval to b-th (one-based) added interval? Answer all the queries. Note, that initially you have an empty set of intervals.

Input: The first line of the input contains integer n denoting the number of queries, (1 ≤ n ≤ 100). Each of the following lines contains a query as described above. All numbers in the input are integers and don't exceed 109 by their absolute value.It's guaranteed that all queries are correct.

Output: For each query of the second type print "YES" or "NO" on a separate line depending on the answer.


Sample Inputs:
5
1 1 5
1 5 11
2 1 2
1 2 9
2 1 2

Sample Outputs:
NO
YES

Solution (Python):
(s, t, i) = ({}, list(), 1)
for n in range(int(input())):
    (c, a, b) = map(int, input().split())
    if c > 1:
        if b in s[a]:
            print('YES')
        else:
            print('NO')
    else:
        s[i] = {i}
        for (j, (x, y)) in enumerate(t, 1):
            if x < a and a < y or (x < b and b < y):
                s[i].update(s[j])
        r = set((j for (j, (x, y)) in enumerate(t, 1) if a < x < b or a < y < b))
        for j in range(1, len(t) + 1):
            if r & s[j]:
                s[j].update(s[i])
        t.append((a, b))
        i += 1

Solution (Python):
n = int(input())
xy = []
adjlist = []

def dfs(visit, cur, dest):
    visit[cur] = True
    if cur == dest:
        return True
    else:
        found = False
        for v in adjlist[cur]:
            if not visit[v]:
                found = found or dfs(visit, v, dest)
        return found
for tc in range(0, n):
    (q, a, b) = [int(x) - 1 for x in input().split()]
    if q == 0:
        adjlist.append([])
        for i in range(0, len(xy)):
            (x, y) = xy[i]
            if a < x < b or a < y < b:
                adjlist[i].append(len(xy))
            if x < a < y or x < b < y:
                adjlist[len(xy)].append(i)
        xy.append((a, b))
    elif q == 1:
        visit = [False for x in range(0, len(xy))]
        if dfs(visit, a, b):
            print('YES')
        else:
            print('NO')

Solution (Python):
(s, t, i) = ({}, [], 1)
for n in range(int(input())):
    (c, a, b) = map(int, input().split())
    if c > 1:
        print('YES' if b in s[a] else 'NO')
    else:
        s[i] = {i}
        for (j, (x, y)) in enumerate(t, 1):
            if x < a < y or x < b < y:
                s[i].update(s[j])
        r = set((j for (j, (x, y)) in enumerate(t, 1) if a < x < b or a < y < b))
        for j in range(1, len(t) + 1):
            if r & s[j]:
                s[j].update(s[i])
        t.append((a, b))
        i += 1