Problem:


Score: 600 points

Problem Statement

After being invaded by the Kingdom of AlDebaran, bombs are planted throughout our country, AtCoder Kingdom.

Fortunately, our military team called ABC has managed to obtain a device that is a part of the system controlling the bombs.

There are N bombs, numbered 1 to N, planted in our country. Bomb i is planted at the coordinate A_i. It is currently activated if B_i=1, and deactivated if B_i=0.

The device has M cords numbered 1 to M. If we cut Cord j, the states of all the bombs planted between the coordinates L_j and R_j (inclusive) will be switched - from activated to deactivated, and vice versa.

Determine whether it is possible to deactivate all the bombs at the same time. If the answer is yes, output a set of cords that should be cut.

Constraints

All values in input are integers.

1 \leq N \leq 10^5

1 \leq A_i \leq 10^9\ (1 \leq i \leq N)

A_i are pairwise distinct.

B_i is 0 or 1. (1 \leq i \leq N)

1 \leq M \leq 2 \times 10^5

1 \leq L_j \leq R_j \leq 10^9\ (1 \leq j \leq M)

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
:
A_N B_N
L_1 R_1
:
L_M R_M

Output

If it is impossible to deactivate all the bombs at the same time, print -1. If it is possible to do so, print a set of cords that should be cut, as follows:

k
c_1 c_2 \dots c_k

Here, k is the number of cords (possibly 0), and c_1, c_2, \dots, c_k represent the cords that should be cut. 1 \leq c_1 < c_2 < \dots < c_k \leq M must hold.

Sample Input 1

3 4
5 1
10 1
8 0
1 10
4 5
6 7
8 9

Sample Output 1

2
1 4

There are two activated bombs at the coordinates 5, 10, and one deactivated bomb at the coordinate 8.

Cutting Cord 1 switches the states of all the bombs planted between the coordinates 1 and 10, that is, all of the three bombs.

Cutting Cord 4 switches the states of all the bombs planted between the coordinates 8 and 9, that is, Bomb 3.

Thus, we can deactivate all the bombs by cutting Cord 1 and Cord 4.

Sample Input 2

4 2
2 0
3 1
5 1
7 0
1 4
4 7

Sample Output 2

-1

Cutting any set of cords will not deactivate all the bombs at the same time.

Sample Input 3

3 2
5 0
10 0
8 0
6 9
66 99

Sample Output 3

0

All the bombs are already deactivated, so we do not need to cut any cord.

Sample Input 4

12 20
536130100 1
150049660 1
79245447 1
132551741 0
89484841 1
328129089 0
623467741 0
248785745 0
421631475 0
498966877 0
43768791 1
112237273 0
21499042 142460201
58176487 384985131
88563042 144788076
120198276 497115965
134867387 563350571
211946499 458996604
233934566 297258009
335674184 555985828
414601661 520203502
101135608 501051309
90972258 300372385
255474956 630621190
436210625 517850028
145652401 192476406
377607297 520655694
244404406 304034433
112237273 359737255
392593015 463983307
150586788 504362212
54772353 83124235

Sample Output 4

5
1 7 8 9 11

If there are multiple sets of cords that deactivate all the bombs when cut, any of them can be printed.



Sample input:
3 4
5 1
10 1
8 0
1 10
4 5
6 7
8 9


Sample output:
2
1 4

Submission status: Wrong Answer

Solution code:

"""
切った時、L以上が全てフリップされ、R+1以上がフリップされると考える
切り方を選んだ時の表裏は座圧BITなどで可能になる

では、どのように良い感じに選ぶか
左から順番に決めていく？
色が左と違うとき、その間に少なくとも一つフリップ基準が存在しなくてはいけない
しかもその中から奇数個選ぶのか…

確かグラフを構成するんだっけ？そこから辺を選択して木を構成する
各点において奇数個、偶数個選ぶのは初期状態で決まる

各連結成分ごとに奇数個が偶数個あったら適当にやって作れる
それ以外は不可能

適当に？→うむ

結論：
まず区間を点に紐づける
→連結成分に分ける(グラフにする)
→dfsなどで木を構成？


もっとシンプルにできるだろ
dfsをメインに考えてみる
どんどん進む
戻るときに、辺を答えに加えるor加えないを選択
"""

import bisect
from collections import deque
import sys

N,M = map(int,input().split())
AB = []

for i in range(N):
    a,b = map(int,input().split())
    AB.append((a,b))
AB.sort()
AB.append((float("inf"),2))
lis = [ [] for i in range(N+1) ]

for i in range(M):
    L,R = map(int,input().split())
    lind = bisect.bisect_left(AB,(L,-1))
    rind = bisect.bisect_left(AB,(R+1,-1))
    
    if lind == rind:
        continue
    lis[lind].append([rind,i])
    lis[rind].append([lind,i])

ans = []
visited = [False] * (N+1)

def dfs(p):
    
    visited[p] = True
    ret = AB[p][1]

    for nex,eind in lis[p]:
        if not visited[nex]:
            cat = dfs(nex)
            if cat == 1:
                ans.append(eind+1)
            ret ^= cat

    return ret

for i in range(N,-1,-1):
    if not visited[i]:
        st = dfs(i)

        if i != N and st != 0:
            print (-1)
            sys.exit()

ans.sort()
print (len(ans))
print (" ".join(map(str,ans)))


#遅すぎる旧解答
""" 
import bisect
from collections import deque
import sys

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

AB = []

for i in range(N):

    a,b = map(int,input().split())
    AB.append((a,b))

AB.sort()
AB.append((float("inf"),2))
lis = [ [] for i in range(N+1) ]

for i in range(M):

    L,R = map(int,input().split())
    lind = bisect.bisect_left(AB,(L,-1))
    rind = bisect.bisect_left(AB,(R+1,-1))

    if lind == rind:
        continue

    lis[lind].append([rind,i])
    lis[rind].append([lind,i])

#print (lis)



each = [None] * N
for i in range(N):
    if i == 0:
        each[i] = AB[i][1]
    elif AB[i][1] == AB[i-1][1]:
        each[i] = 0
    else:
        each[i] = 1
each.append(2)

#print ("each:" ,each)

dep = [float("inf")] * (N+1)
ind = N
numlink = [0] * (N+1)
ans = []
plis = [i for i in range(N)]

while ind >= 0:

    if dep[ind] != float("inf"):
        ind -= 1
        continue
    else:
        q = [ind]
        ni = 0

        templis = [ind]
        dep[ind] = 0
        elis = [None]

        while ni < len(q):

            now = q[ni]
            ni += 1
            for nex,eind in lis[now]:
                if dep[nex] > dep[now] + 1:
                    
                    dep[nex] = dep[now] + 1
                    q.append(nex)
                    templis.append(nex)
                    elis.append(eind)
                    numlink[now] += 1
                    numlink[nex] += 1
                    plis[nex] = now

        #print ("tl:",templis)
        #print ("el:",elis)
        #print ("numlink:" , numlink)
        #print ("dep:" , dep)
        
        
        for i in range(len(templis)-1 , 0 , -1):

            if each[templis[i]] != numlink[templis[i]] % 2:
                numlink[plis[templis[i]]] -= 1
                numlink[templis[i]] -= 1
            else:
                ans.append(elis[i]+1)

        #print ("tl:",templis)
        #print ("el:",elis)
        #print ("numlink:" , numlink)
        #print ("dep:" , dep)
        

        if each[templis[0]] != 2 and each[templis[0]] != numlink[templis[0]] % 2:
            print (-1)
            sys.exit()

ans.sort()
print (len(ans))
print (" ".join(map(str,ans)))
"""

Submission status: Wrong Answer

Solution code:

"""
切った時、L以上が全てフリップされ、R+1以上がフリップされると考える
切り方を選んだ時の表裏は座圧BITなどで可能になる

では、どのように良い感じに選ぶか
左から順番に決めていく？
色が左と違うとき、その間に少なくとも一つフリップ基準が存在しなくてはいけない
しかもその中から奇数個選ぶのか…

確かグラフを構成するんだっけ？そこから辺を選択して木を構成する
各点において奇数個、偶数個選ぶのは初期状態で決まる

各連結成分ごとに奇数個が偶数個あったら適当にやって作れる
それ以外は不可能

適当に？→うむ

結論：
まず区間を点に紐づける
→連結成分に分ける(グラフにする)
→dfsなどで木を構成？
"""
import bisect
from collections import deque
import sys

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

AB = []

for i in range(N):

    a,b = map(int,input().split())
    AB.append((a,b))

AB.sort()
AB.append((float("inf"),2))
lis = [ [] for i in range(N+1) ]

for i in range(M):

    L,R = map(int,input().split())
    lind = bisect.bisect_left(AB,(L,-1))
    rind = bisect.bisect_left(AB,(R+1,-1))

    if lind == rind:
        continue

    lis[lind].append([rind,i])
    lis[rind].append([lind,i])

#print (lis)

each = [None] * N
for i in range(N):
    if i == 0:
        each[i] = AB[i][1]
    elif AB[i][1] == AB[i-1][1]:
        each[i] = 0
    else:
        each[i] = 1
each.append(2)

#print ("each:" ,each)

dep = [float("inf")] * (N+1)
ind = N
numlink = [0] * (N+1)
ans = []
plis = [i for i in range(N)]

while ind >= 0:

    if dep[ind] != float("inf"):
        ind -= 1
        continue
    else:
        q = deque([ind])

        templis = [ind]
        dep[ind] = 0
        elis = [None]

        while len(q) > 0:

            now = q.popleft()
            for nex,eind in lis[now]:
                if dep[nex] > dep[now] + 1:
                    
                    dep[nex] = dep[now] + 1
                    q.append(nex)
                    templis.append(nex)
                    elis.append(eind)
                    numlink[now] += 1
                    numlink[nex] += 1
                    plis[nex] = now

        #print ("tl:",templis)
        #print ("el:",elis)
        #print ("numlink:" , numlink)
        #print ("dep:" , dep)
        
        
        for i in range(len(templis)-1 , 0 , -1):

            if each[templis[i]] != numlink[templis[i]] % 2:
                numlink[plis[templis[i]]] -= 1
                numlink[templis[i]] -= 1
            else:
                ans.append(elis[i]+1)

        #print ("tl:",templis)
        #print ("el:",elis)
        #print ("numlink:" , numlink)
        #print ("dep:" , dep)
        

        if each[templis[0]] != 2 and each[templis[0]] != numlink[templis[0]] % 2:
            print (-1)
            sys.exit()

print (len(ans))
print (" ".join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

N, M = map(int, input().split())
R = []
for _ in range(N):
    a, b = map(int, input().split())
    R.append((a*2, b, 0, 0))
for i in range(M):
    l, r = map(int, input().split())
    R.append((l*2-1, 2, -1, i))
    R.append((r*2+1, 3, 2*l-1, i))

R.sort(key=lambda x:x[0])
nodeid = 0
bf = -1
d = dict()
x2id = dict()
id2eid = dict()
G = {0:set()}
for x, f, l, i in R:
    if f <= 1:
        d[nodeid] = int(f != bf and bf != -1)
        bf = f
        nodeid += 1
        G[nodeid] = set()
    else:
        x2id[x] = nodeid
        if f == 3:
#            print(x2id, l)
            G[nodeid].add(x2id[l])
            G[x2id[l]].add(nodeid)
            id2eid[(nodeid, x2id[l])] = i
            id2eid[(x2id[l], nodeid)] = i
d[nodeid] = int(bf == 1)

def iterf(v):
    r = d[v]
    for u in G[v]:
        if u in vs:
            continue
        vs.add(u)
        avs.add(u)
        ff = iterf(u)
        if ff:
            cut_edges.add((v, u))
        r = (r+ff)%2
    return r if v != 0 else 0

xxs = [-1]*nodeid
avs = set()
cut_edges = set()
for i in range(nodeid+1):
    if i in avs:
        continue
    vs = set([i])
    rr = iterf(i)
    if rr:
        print(-1)
        break
else:
#    print(G)
#    print(d)

    print(len(cut_edges))
    print(*[id2eid[(x, y)]+1 for x, y in cut_edges])

Submission status: Wrong Answer

Solution code:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


# 解説
N, M = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]
LR = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
AB = np.array(AB, dtype=int)
LR = np.array(LR, dtype=int)

AB = AB[np.argsort(AB[:, 0])]
A, B = AB[:, 0], AB[:, 1]
L, R = LR[:, 0], LR[:, 1]

L = np.searchsorted(A, L, side='left').tolist()
R = np.searchsorted(A, R, side='right').tolist()

# L か R の数が奇数になる場所が True
is_odd = np.diff(np.concatenate(([0], B, [0]))) != 0

graph = [[] for _ in range(N + 1)]
for i, (l, r) in enumerate(list(zip(L, R))):
    graph[l].append((r, i))
    graph[r].append((l, i))

seen_graph = [False] * (N + 1)
seen_v = [False] * (N + 1)
parents = [None] * (N + 1)


def dfs(v):
    # 子の is_odd の数が奇数ならその辺を切る。葉からやってけば root で辻褄が合う
    ret = int(is_odd[v])
    for u, j in graph[v]:
        if seen_v[u]:
            continue
        seen_v[u] = True
        children_odds = dfs(u)
        if children_odds % 2 == 1:
            ans.append(j)
        ret += children_odds
    return ret


ans = []
for v in range(N + 1):
    if seen_v[v]:
        continue
    seen_v[v] = True
    ans = []
    if dfs(v) % 2 != 0:
        print(-1)
        exit()

ans = np.array(ans, dtype=int)
ans.sort()
print(len(ans))
print(*(ans + 1))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
import numpy as np
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,m = LI()
ab = [LI() for _ in range(n)]
lr = [LI() for _ in range(m)]
ab.sort()
X = [i for i,j in ab]
b = [j for i,j in ab]
s = sum(b)
if s == 0:
    print(0)
    quit()
B = np.array([])
for i in b:
    B = np.append(B,np.array([i]))

A = np.empty((0,n),int)
for l,r in lr:
    L = bl(X,l)
    R = br(X,r)
    a = [0]*(n+1)
    a[L] += 1
    a[R] -= 1
    a = list(accumulate(a))
    A = np.append(A,np.array([a[:-1]]),axis = 0)

inv_A = np.linalg.pinv(A)
ans = np.dot(B,inv_A)
ans = list(ans)
ans = list(map(lambda x:abs(x),ans))

cnt = 0
lst = []
for i in range(m):
    if 0.8 <= ans[i] < 1.2:
        lst.append(i+1)
        cnt += 1
if cnt == 0:
    print(-1)
    quit()
print(cnt)
print(*lst)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
import numpy as np
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,m = LI()
ab = [LI() for _ in range(n)]
lr = [LI() for _ in range(m)]
ab.sort()
X = [i for i,j in ab]
b = [j for i,j in ab]
s = sum(b)
if s == 0:
    print(0)
    quit()
B = np.array([])
for i in b:
    B = np.append(B,np.array([i]))

A = np.empty((0,n),int)
for l,r in lr:
    L = bl(X,l)
    R = br(X,r)
    a = np.array([])
    for j in range(L):
        a = np.append(a,np.array([0]))
    for j in range(L,R):
        a = np.append(a,np.array([1]))
    for j in range(R,n):
        a = np.append(a,np.array([0]))
    A = np.append(A,[a],axis = 0)

inv_A = np.linalg.pinv(A)
ans = np.dot(B,inv_A)
ans = list(ans)
ans = list(map(lambda x:abs(x),ans))

cnt = 0
lst = []
for i in range(m):
    if 0.5 <= ans[i] < 1.5:
        lst.append(i+1)
        cnt += 1
if cnt == 0:
    print(-1)
    quit()
print(cnt)
print(*lst)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bl, bisect_right as br
from collections import deque
N, M = map(int, input().split())
A = [0] * N
B = [0] * N
for i in range(N):
    a, b = map(int, input().split())
    A[i] = a
    B[i] = b

S = sorted(A)
D = {a: i for i, a in enumerate(S)}

BB = [0] * (N+1)
for i in range(N):
    BB[D[A[i]] + 1] = B[i]

for i in range(1, N+1):
    BB[i-1] ^= BB[i]

A = [D[a] for a in A]
X = [[] for _ in range(N+1)]
DD = {}
for i in range(M):
    l, r = map(int, input().split())
    l = bl(S, l)
    r = bl(S, r+1)
    X[l].append(r)
    X[r].append(l)
    DD[(l<<18) + r] = i
    DD[(r<<18) + l] = i

Q = deque([i for i in range(N+1)])
P = [-1] * (N+1)
CH = [[] for _ in range(N+1)]
R = []
while Q:
    i = deque.popleft(Q)
    if P[i] < 0: R.append(i)
    for j in X[i]:
        if P[j] >= 0: continue
        if j != P[i]:
            R.append(j)
            P[j] = i
            CH[i].append(j)
            X[j].remove(i)
            deque.append(Q, j)

ANS = []
for i in R[1:][::-1]:
    if BB[i]:
        BB[i] ^= 1
        BB[P[i]] ^= 1
        if P[i] < 0:
            print(-1)
            exit()
        ANS.append(DD[(i<<18) + P[i]] + 1)
if sum(BB) == 0:
    print(len(ANS))
    print(*sorted(ANS))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bl, bisect_right as br
from collections import deque
N, M = map(int, input().split())
A = [0] * N
B = [0] * N
for i in range(N):
    a, b = map(int, input().split())
    A[i] = a
    B[i] = b

S = sorted(A)
D = {a: i for i, a in enumerate(S)}

BB = [0] * (N+1)
for i in range(N):
    BB[D[A[i]] + 1] = B[i]

for i in range(1, N+1):
    BB[i-1] ^= BB[i]

A = [D[a] for a in A]
X = [[] for _ in range(N+1)]
DD = {}
for i in range(M):
    l, r = map(int, input().split())
    l = bl(S, l)
    r = bl(S, r+1)
    X[l].append(r)
    X[r].append(l)
    DD[(l<<18) + r] = i
    DD[(r<<18) + l] = i

Q = deque([i for i in range(N+1)])
P = [-1] * (N+1)
CH = [[] for _ in range(N+1)]
R = []
while Q:
    i = deque.popleft(Q)
    if P[i] < 0: R.append(i)
    for j in X[i]:
        if P[j] >= 0: continue
        if j != P[i]:
            R.append(j)
            P[j] = i
            CH[i].append(j)
            X[j].remove(i)
            deque.append(Q, j)

ANS = []
for i in R[1:][::-1]:
    if BB[i]:
        BB[i] ^= 1
        BB[P[i]] ^= 1
        if P[i] < 0:
            print(-1)
            exit()
        ANS.append(DD[(i<<18) + P[i]] + 1)
if sum(BB) == 0:
    print(len(ANS))
    print(*ANS)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import bisect
def merge(is_1, is_2):
    r = []
    i1, i2 = 0, 0
    while i1 < len(is_1) and i2 < len(is_2):
        if is_1[i1] == is_2[i2]:
            i1 += 1
            i2 += 1
        elif is_1[i1] < is_2[i2]:
            r.append(is_1[i1])
            i1 += 1
        else:
            r.append(is_2[i2])
            i2 += 1
    for i in range(i1,len(is_1)):
        r.append(is_1[i])
    for i in range(i2,len(is_2)):
        r.append(is_2[i])
    return r

def disjoint(is_1, is_2):
    s = set(is_1 + is_2)
    return len(s) == len(is_1)  + len(is_2)

def solve(bombs, sws):
    if sum(bombs) == 0:
        return []
    #print('bombs', bombs)
    #print('sws', sws)
    starts = [[] for _ in bombs]
    links = [None for _ in bombs]
    for (l, r, i) in sws:
        starts[l].append([r, [i]])
    for i in range(len(bombs)):
        if len(starts[i]) <= 0:
            continue
        d = {}
        #print('i=', i, 'starts[i]=', starts[i])
        for r, i_s in starts[i]:
            if r in d:
                if len(d[r]) > len(i_s):
                    d[r] = i_s
            else:
                d[r] = i_s
        #print(d)
        ds = sorted(d)
        links[i] = (ds[0], d[ds[0]])
        for i in range(1, len(ds)):
            starts[ds[i - 1]].append([ds[i], merge(d[ds[i - 1]], d[ds[i]])])
            # if disjoint(d[ds[i - 1]], d[ds[i]]):
            # starts[ds[i - 1]].append([ds[i], merge(d[ds[i - 1]], d[ds[i]])])
    # print(starts)
    # print(links)
    r = []
    for i in range(len(bombs)):
        if bombs[i] == 0:
            continue
        if links[i] is None:
            return None
        #print('i=', i, ',bombs=', bombs, 'links[i]=', links[i], ',r=', r)
        for j in range(i, links[i][0]):
            bombs[j] = 1 - bombs[i]
        r = merge(r, links[i][1])
    return r

n, m = [int(x) for x in input().split()]
bombs = [tuple(int(x) for x in input().split()) for _ in range(n)]
bombs.sort()
sws = []
for i in range(m):
    l, r = [int(x) for x in input().split()]
    l = bisect.bisect_left(bombs, (l, 0))
    r = bisect.bisect_right(bombs, (r, 1))
    if l != r:
        sws.append((l, r, i + 1))
bombs = [x[1] for x in bombs]
sws.sort()
r = solve(bombs, sws)
if r is None:
    print(-1)
else:
    print(len(r))
    print(' '.join(str(x) for x in r))

Submission status: Wrong Answer

Solution code:
import bisect
def merge(is_1, is_2):
    r = []
    i1, i2 = 0, 0
    while i1 < len(is_1) and i2 < len(is_2):
        if is_1[i1] == is_2[i2]:
            i1 += 1
            i2 += 1
        elif is_1[i1] < is_2[i2]:
            r.append(is_1[i1])
            i1 += 1
        else:
            r.append(is_2[i2])
            i2 += 1
    for i in range(i1,len(is_1)):
        r.append(is_1[i])
    for i in range(i2,len(is_2)):
        r.append(is_2[i])
    return r

def disjoint(is_1, is_2):
    s = set(is_1 + is_2)
    return len(s) == len(is_1)  + len(is_2)

def solve(bombs, sws):
    if sum(bombs) == 0:
        return []
    #print('bombs', bombs)
    #print('sws', sws)
    starts = [[] for _ in bombs]
    links = [None for _ in bombs]
    for (l, r, i) in sws:
        starts[l].append([r, [i]])
    for i in range(len(bombs)):
        if len(starts[i]) <= 0:
            continue
        d = {}
        #print('i=', i, 'starts[i]=', starts[i])
        for r, i_s in starts[i]:
            if r in d:
                if len(d[r]) > len(i_s):
                    d[r] = i_s
            else:
                d[r] = i_s
        #print(d)
        ds = sorted(d)
        links[i] = (ds[0], d[ds[0]])
        for i in range(1, len(ds)):
            if disjoint(d[ds[i - 1]], d[ds[i]]):
                starts[ds[i - 1]].append([ds[i], merge(d[ds[i - 1]], d[ds[i]])])
    # print(starts)
    # print(links)
    r = []
    for i in range(len(bombs)):
        if bombs[i] == 0:
            continue
        if links[i] is None:
            return None
        #print('i=', i, ',bombs=', bombs, 'links[i]=', links[i], ',r=', r)
        for j in range(i, links[i][0]):
            bombs[j] = 1 - bombs[i]
        r = merge(r, links[i][1])
    return r

n, m = [int(x) for x in input().split()]
bombs = [tuple(int(x) for x in input().split()) for _ in range(n)]
bombs.sort()
sws = []
for i in range(m):
    l, r = [int(x) for x in input().split()]
    l = bisect.bisect_left(bombs, (l, 0))
    r = bisect.bisect_right(bombs, (r, 1))
    if l != r:
        sws.append((l, r, i + 1))
bombs = [x[1] for x in bombs]
sws.sort()
r = solve(bombs, sws)
if r is None:
    print(-1)
else:
    print(len(r))
    print(' '.join(str(x) for x in r))

Submission status: Wrong Answer

Solution code:
import bisect
def merge(is_1, is_2):
    r = []
    i1, i2 = 0, 0
    while i1 < len(is_1) and i2 < len(is_2):
        if is_1[i1] == is_2[i2]:
            i1 += 1
            i2 += 1
        elif is_1[i1] < is_2[i2]:
            r.append(is_1[i1])
            i1 += 1
        else:
            r.append(is_2[i2])
            i2 += 1
    for i in range(i1,len(is_1)):
        r.append(is_1[i])
    for i in range(i2,len(is_2)):
        r.append(is_2[i])
    return r

def solve(bombs, sws):
    if sum(bombs) == 0:
        return []
    # print('bombs', bombs)
    # print('sws', sws)
    starts = [[] for _ in bombs]
    links = [None for _ in bombs]
    for (l, r, i) in sws:
        starts[l].append([r, [i]])
    for i in range(len(bombs)):
        if len(starts[i]) <= 0:
            continue
        d = {}
        for r, i_s in starts[i]:
            d[r] = i_s
        ds = sorted(d)
        links[i] = (ds[0], d[ds[0]])
        for i in range(1, len(ds)):
            starts[ds[i - 1]].append([ds[i], merge(d[ds[i - 1]], d[ds[i]])])
    # print(starts)
    # print(links)
    r = []
    for i in range(len(bombs)):
        if bombs[i] == 0:
            continue
        if links[i] is None:
            return None
        for j in range(i, links[i][0]):
            bombs[i] = 1 - bombs[i]
        r = merge(r, links[i][1])
    return r

n, m = [int(x) for x in input().split()]
bombs = [tuple(int(x) for x in input().split()) for _ in range(n)]
bombs.sort()
sws = []
for i in range(m):
    l, r = [int(x) for x in input().split()]
    l = bisect.bisect_left(bombs, (l, 0))
    r = bisect.bisect_right(bombs, (r, 1))
    if l != r:
        sws.append((l, r, i + 1))
bombs = [x[1] for x in bombs]
sws.sort()
r = solve(bombs, sws)
if r is None:
    print(-1)
else:
    print(len(r))
    print(' '.join(str(x) for x in r))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

def b_search(key, r=0, *, l=-1):
    #左側がkeyをFalseにし、右側がkeyをTrueにするような1次元配列に対して、keyをFalseに最大のindexとkeyをTrueにする最小のindexを求める
    while r-l-1: m = (l+r)//2; l,r = (l,m) if key(m) else (m,r)
    return l,r

def solve():
    N, M = map(int, input().split())
    L = sorted([tuple(map(int, input().split())) for _  in range(N)])

    A = [0]+[l[0] for l in L]+[10**9+1]

    b = ''.join([str(l[1]) for l in L])+'0'
    c = [0]+[int(b[i]!=b[i+1]) for i in range(N)]
    E = [set() for _ in range(N+1)]
    E_ = [(0,0)]
    for i in range(1,M+1):
        l,r = map(int, input().split())
        u = b_search(lambda i: A[i]>=l,r=N+1,l=0)[0]
        v = b_search(lambda i: A[i]>r,r=N+1,l=0)[0]
        E[u].add((v,i))
        E[v].add((u,-i))
        E_.append((u,v))
    E_ += [e[::-1] for e in E_[:0:-1]]
    V = list(range(N,-1,-1))
    F = []
    while V:
        q = [(V[-1],0)]
        while q:
            u,i = q.pop()
            if u in V:
                V.remove(u)
                F.append(i)
                for v,j in E[u]:
                    if v in V:
                        q.append((v,j))
    R = []
    for f in F[:0:-1]:
        u,v = E_[f]
        if c[v]%2:
            c[u] += 1
            c[v] += 1
            R.append(str(abs(f)))
    res = str(len(R)) + '\n' +' '.join(R[::-1])
    if any(a%2 for a in c[1:]):
        return '-1'
    else:
        return str(res)

if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

def b_search(key, r=0, *, l=-1):
    #左側がkeyをFalseにし、右側がkeyをTrueにするような1次元配列に対して、keyをFalseに最大のindexとkeyをTrueにする最小のindexを求める
    while r-l-1: m = (l+r)//2; l,r = (l,m) if key(m) else (m,r)
    return l,r

def solve():
    N, M = map(int, input().split())
    L = sorted([tuple(map(int, input().split())) for _  in range(N)])

    A = [0]+[l[0] for l in L]+[10**9+1]

    b = ''.join([str(l[1]) for l in L])+'0'
    c = [0]+[int(b[i]!=b[i+1]) for i in range(N)]
    E = [set() for _ in range(N+1)]
    E_ = [(0,0)]
    for i in range(1,M+1):
        l,r = map(int, input().split())
        u = b_search(lambda i: A[i]>=l,r=N+1,l=0)[0]
        v = b_search(lambda i: A[i]>r,r=N+1,l=0)[0]
        E[u].add((v,i))
        E[v].add((u,-i))
        E_.append((u,v))
    E_ += [e[::-1] for e in E_[:0:-1]]
    V = list(range(N,-1,-1))
    F = []
    while V:
        q = [(V[-1],0)]
        while q:
            u,i = q.pop()
            if u in V:
                V.remove(u)
                F.append(i)
                for v,j in E[u]:
                    if v in V:
                        q.append((v,j))
    R = []
    for f in F[:0:-1]:
        u,v = E_[f]
        if c[v]%2:
            c[u] += 1
            c[v] += 1
            R.append(str(abs(f)))
    res = str(len(R)) + '\n' +' '.join(R)
    if any(a%2 for a in c[1:]):
        return '-1'
    else:
        return str(res)

if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

def b_search(key, r=0, *, l=-1):
    #左側がkeyをFalseにし、右側がkeyをTrueにするような1次元配列に対して、keyをFalseに最大のindexとkeyをTrueにする最小のindexを求める
    while r-l-1: m = (l+r)//2; l,r = (l,m) if key(m) else (m,r)
    return l,r

def solve():
    N, M = map(int, input().split())
    L = sorted([tuple(map(int, input().split())) for _  in range(N)])

    A = [0]+[l[0] for l in L]+[10**9+1]

    b = ''.join([str(l[1]) for l in L])+'0'
    c = [0]+[int(b[i]!=b[i+1]) for i in range(N)]
    E = [set() for _ in range(N+1)]
    E_ = [(0,0)]
    key = lambda a: (lambda i: A[i]>a)
    for i in range(1,M+1):
        l,r = map(int, input().split())
        u = b_search(key(l),r=N+1,l=0)[0]
        v = b_search(key(r),r=N+1,l=0)[0]
        E[u].add((v,i))
        E[v].add((u,-i))
        E_.append((u,v))
    E_ += [e[::-1] for e in E_[:0:-1]]

    V = list(range(N,-1,-1))
    F = []
    while V:
        q = [(V[-1],0)]
        while q:
            u,i = q.pop()
            if u in V:
                V.remove(u)
                F.append(i)
                for v,j in E[u]:
                    if v in V:
                        q.append((v,j))
    R = []
    for f in F[:0:-1]:
        u,v = E_[f]
        if c[v]%2:
            c[u] += 1
            c[v] += 1
            R.append(str(abs(f)))
    res = str(len(R)) + '\n' +' '.join(R)
    return str(res)

if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
def solve():
    N, M = map(int, input().split())
    L = sorted([tuple(map(int, input().split())) for _  in range(N)])
    A = [l[0] for l in L]
    b = int(''.join([str(l[1]) for l in L]),2)
    K = [tuple(map(int, input().split())) for _  in range(M)]

    LR = sorted([int(''.join(['1' if l <= a <= r else '0' for a in A]),2) for l,r in K], reverse=1)

    #print(f'{b:0>{N:d}b}')
    #for lr in LR:
    #    print(f'{lr:0>{N:d}b}')
    res = 0
    return str(res)

if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

Solution code:
import bisect

n, m = map(int, input().split()) 

ab = sorted([list(map(int, input().split())) for _ in range(n)])
a = [ai for ai, bi in ab]
b = [bi for ai, bi in ab]

evs = []
for i in range(m):
  l, r = map(int, input().split())
  evs.append((l, i + 1, "l", bisect.bisect_left(a, l, lo=0, hi=n)))
  evs.append((r, i + 1, "r", bisect.bisect_right(a, r, lo=0, hi=n)))
evs.sort()

j = bisect.bisect_right(a, evs[0][0], lo=0, hi=n)
if any(bi == 1 for bi in b[0:j]):
  print(-1)
  exit()

cut= set()
switched = False
evs_len = 2 * m
for i, ev in enumerate(evs):
  if ev[2] == "l":
    next_ev = evs[i+1]    
    if all(bi != switched for bi in b[ev[3]:next_ev[3]]):
      cut.add(ev[1])
      switched = not switched
    elif all(bi == switched for bi in b[ev[3]:next_ev[3]]):
      pass
    else:
      print(-1)
      exit()
  elif ev[2] == "r": 
    if ev[1] in cut:
      switched = not switched
    if all(bi == switched for bi in b[ev[3]:next_ev[3]]):
      pass
    else:
      print(-1)
      exit()

print(len(cut))
print(" ".join(map(str, sorted(cut))))

Submission status: Wrong Answer

Solution code:
import bisect

n, m = map(int, input().split()) 

ab = sorted([list(map(int, input().split())) for _ in range(n)])
a = [ai for ai, bi in ab]
b = [bi for ai, bi in ab]

evs = []
for i in range(m):
  l, r = map(int, input().split())
  evs.append((l, i + 1, "l"))
  evs.append((r, i + 1, "r"))
evs.sort()

j = bisect.bisect_right(a, evs[0][0], lo=0, hi=n)
if any(bi == 1 for bi in b[0:j]):
  print(-1)
  exit()

cut= set()
switched = False
evs_len = 2 * m
for i, ev in enumerate(evs):
  if ev[2] == "l":
    next_ev = evs[i+1]    
    j = bisect.bisect_left(a, ev[0], lo=0, hi=n)
    k = bisect.bisect_right(a, next_ev[0], lo=0, hi=n)
    if all(bi != switched for bi in b[j:k]):
      cut.add(ev[1])
      switched = not switched
    elif all(bi == switched for bi in b[j:k]):
      pass
    else:
      print(-1)
      exit()
  elif ev[2] == "r": 
    if ev[1] in cut:
      switched = not switched
    next_ev = evs[i+1] if i != evs_len - 1 else (999999999999,0,0)
    j = bisect.bisect_right(a, ev[0], lo=0, hi=n)
    k = bisect.bisect_left(a, next_ev[0], lo=0, hi=n)
    if all(bi == switched for bi in b[j:k]):
      pass
    else:
      print(-1)
      exit()

print(len(cut))
print(" ".join(map(str, sorted(cut))))