Tracking Segments (Codeforces 1843E)
Tags: Others, two pointers

You are given an array $$$a$$$ consisting of $$$n$$$ zeros. You are also given a set of $$$m$$$ not necessarily different segments. Each segment is defined by two numbers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) and represents a subarray $$$a_{l_i}, a_{l_i+1}, \dots, a_{r_i}$$$ of the array $$$a$$$.Let's call the segment $$$l_i, r_i$$$ beautiful if the number of ones on this segment is strictly greater than the number of zeros. For example, if $$$a = [1, 0, 1, 0, 1]$$$, then the segment $$$[1, 5]$$$ is beautiful (the number of ones is $$$3$$$, the number of zeros is $$$2$$$), but the segment $$$[3, 4]$$$ is not is beautiful (the number of ones is $$$1$$$, the number of zeros is $$$1$$$).You also have $$$q$$$ changes. For each change you are given the number $$$1 \le x \le n$$$, which means that you must assign an element $$$a_x$$$ the value $$$1$$$.You have to find the first change after which at least one of $$$m$$$ given segments becomes beautiful, or report that none of them is beautiful after processing all $$$q$$$ changes.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le m \le n \le 10^5$$$) — the size of the array $$$a$$$ and the number of segments, respectively.Then there are $$$m$$$ lines consisting of two numbers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) —the boundaries of the segments.The next line contains an integer $$$q$$$ ($$$1 \le q \le n$$$) — the number of changes.The following $$$q$$$ lines each contain a single integer $$$x$$$ ($$$1 \le x \le n$$$) — the index of the array element that needs to be set to $$$1$$$. It is guaranteed that indexes in queries are distinct.It is guaranteed that the sum of $$$n$$$ for all test cases does not exceed $$$10^5$$$.

Output: For each test case, output one integer  — the minimum change number after which at least one of the segments will be beautiful, or $$$-1$$$ if none of the segments will be beautiful.

Note: In the first case, after first 2 changes we won't have any beautiful segments, but after the third one on a segment $$$[1; 5]$$$ there will be 3 ones and only 2 zeros, so the answer is 3.In the second case, there won't be any beautiful segments.

Sample Inputs:
6
5 5
1 2
4 5
1 5
1 3
2 4
5
5
3
1
2
4
4 2
1 1
4 4
2
2
3
5 2
1 5
1 5
4
2
1
3
4
5 2
1 5
1 3
5
4
1
2
3
5
5 5
1 5
1 5
1 5
1 5
1 4
3
1
4
3
3 2
2 2
1 3
3
2
3
1

Sample Outputs:
3
-1
3
3
3
1

Solution (Python):
import sys

def solve():
    (n, m) = map(int, input().split(' '))
    intervals = []
    for i in range(m):
        (l, r) = map(int, input().split())
        l = l - 1
        intervals.append((l, r))
    q = int(input())
    changes = [0] * q
    for i in range(q):
        changes[i] = int(input())
        changes[i] = changes[i] - 1
    L = 0
    R = q + 1
    lines = 0
    while R - L > 1:
        M = (R + L) // 2
        curState = [0] * n
        for i in range(M):
            curState[changes[i]] = 1
        prevOnes = [0] * (n + 1)
        for i in range(n):
            prevOnes[i + 1] = prevOnes[i] + curState[i]
        ok = False
        for intrv in intervals:
            (l, r) = (intrv[0], intrv[1])
            if prevOnes[r] - prevOnes[l] > (r - l) // 2:
                ok = True
                break
        if ok:
            R = M
        else:
            L = M
        if lines < 10:
            lines += 1
    if R == q + 1:
        R = -1
    print(R)
t = int(input())
for i in range(t):
    solve()

Solution (Python):
def solve():
    (n, m) = map(int, input().split())
    segs = []
    for i in range(m):
        (l, r) = map(int, input().split())
        l -= 1
        segs.append([l, r])
    q = int(input())
    ord = [0] * q
    for i in range(q):
        ord[i] = int(input())
        ord[i] -= 1
    l = 0
    r = q + 1
    while r - l > 1:
        M = (l + r) // 2
        cur = [0] * n
        for i in range(M):
            cur[ord[i]] = 1
        pr = [0] * (n + 1)
        for i in range(n):
            pr[i + 1] = pr[i] + cur[i]
        ok = False
        for i in segs:
            if pr[i[1]] - pr[i[0]] > (i[1] - i[0]) // 2:
                ok = True
                break
        if ok:
            r = M
        else:
            l = M
    if r == q + 1:
        r = -1
    print(r)
tc = int(input())
for T in range(tc):
    solve()

Solution (Python):
def solve():
    (n, m) = map(int, input().split())
    segs = []
    for i in range(m):
        (l, r) = map(int, input().split())
        l -= 1
        segs.append([l, r])
    q = int(input())
    ord = [0] * q
    for i in range(q):
        ord[i] = int(input())
        ord[i] -= 1
    l = 0
    r = q + 1
    while r - l > 1:
        M = (l + r) // 2
        cur = [0] * n
        for i in range(M):
            cur[ord[i]] = 1
        pr = [0] * (n + 1)
        for i in range(n):
            pr[i + 1] = pr[i] + cur[i]
        ok = False
        for i in segs:
            if pr[i[1]] - pr[i[0]] > (i[1] - i[0]) // 2:
                ok = True
                break
        if ok:
            r = M
        else:
            l = M
    if r == q + 1:
        r = -1
    print(r)
tc = int(input())
for T in range(tc):
    solve()