TnT/Multi_CodeNet4Repair huggingface dataset:
Problem: An SNS has N users - User 1, User 2, \cdots, User N.  Between these N users, there are some relationships - M _friendships_ and K _blockships_.  For each i = 1, 2, \cdots, M, there is a bidirectional friendship between User A_i and User B_i.  For each i = 1, 2, \cdots, K, there is a bidirectional blockship between User C_i and User D_i.  We define User a to be a _friend candidate_ for User b when all of the following four conditions are satisfied:    * a \neq b.   * There is not a friendship between User a and User b.   * There is not a blockship between User a and User b.   * There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a, c_L = b, and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1.  For each user i = 1, 2, ... N, how many friend candidates does it have?

Submission attempts (in order):
a, b = [0] * m, [0] * m
c, d = [0] * k, [0] * k

direct =[[] for _ in range(n)]
uf = UnionFind(n)

for i in range(m):
    a[i], b[i] = map(int, input().split())
    a[i] -= 1
    b[i] -= 1
    direct[a[i]].append(b[i])
    direct[b[i]].append(a[i])
    uf.union(a[i], b[i])

for i in range(k):
    c[i], d[i] = map(int, input().split())
    c[i] -= 1
    d[i] -= 1
    if uf.same(c[i], d[i]):
        direct[c[i]].append(d[i])
        direct[d[i]].append(c[i])

ans = [0] * n
for i in range(n):
    ans[i] = uf.size(i) - len(direct[i]) - 1

print(*ans)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1] * n
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.find(x) > self.find(y):
            x, y = y, x
        self.par[x] += self.par[y]
        self.par[y] = x
    def size(self, x):
        return -self.par[(self.find(x))]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.par) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n, m, k = map(int, input().split())
a, b = [0] * m, [0] * m
c, d = [0] * k, [0] * k

direct =[[] for _ in range(n)]
uf = UnionFind(n)

for i in range(m):
    a[i], b[i] = map(int, input().split())
    a[i] -= 1
    b[i] -= 1
    direct[a[i]].append(b[i])
    direct[b[i]].append(a[i])
    uf.union(a[i], b[i])

for i in range(k):
    c[i], d[i] = map(int, input().split())
    c[i] -= 1
    d[i] -= 1
    if uf.same(c[i], d[i]):
        direct[c[i]].append(d[i])
        direct[d[i]].append(c[i])

ans = [0] * n
for i in range(n):
    ans[i] = uf.size(i) - len(direct[i]) - 1

print(*ans)

Verdicts: Runtime Error

Accepted
Problem: An SNS has N users - User 1, User 2, \cdots, User N.  Between these N users, there are some relationships - M _friendships_ and K _blockships_.  For each i = 1, 2, \cdots, M, there is a bidirectional friendship between User A_i and User B_i.  For each i = 1, 2, \cdots, K, there is a bidirectional blockship between User C_i and User D_i.  We define User a to be a _friend candidate_ for User b when all of the following four conditions are satisfied:    * a \neq b.   * There is not a friendship between User a and User b.   * There is not a blockship between User a and User b.   * There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a, c_L = b, and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1.  For each user i = 1, 2, ... N, how many friend candidates does it have?

Submission attempts (in order):
import sys

line = sys.stdin.readline().strip()
n,m,k = map(int, line.split())
roots = list(range(n))
linked = [0]*n
for i in range(m):
    line = sys.stdin.readline().strip()
    a,b = map(int, line.split())
    c, d = min(a,b)-1, max(a,b) - 1
    linked[c] += 1 
    linked[d] += 1
    while c != roots[c]:
        c = roots[c]
    while d != roots[d]:
        d = roots[d]
    e,f = min(c,d), max(c,d)
    roots[f] = e


for i in range(n):
    cursor = i
    while cursor != roots[cursor]:
        cursor = roots[cursor]
    roots[i] = cursor

print(roots)
res = [0]*n
for i in range(k):
    line = sys.stdin.readline().strip()
    a,b = map(int, line.split())
    c,d = a-1, b-1
    # same group blacklist
    if roots[c] == roots[d]:
        res[c] -= 1
        res[d] -= 1 
set_sizes = dict()

rs = list(set(roots))
for r in rs:
    count = 0
    for one in roots:
        if one == r:
            count += 1
    set_sizes[r] = count

for i in range(n):
    r = roots[i]
    res[i] += (set_sizes[r]-1-linked[i])
print (" ".join(map(str, res)))

import sys

line = sys.stdin.readline().strip()
n,m,k = map(int, line.split())
roots = [-1]*n
linked = [0]*n
def find_root(x):
    if roots[x] < 0:
        return x
    else:
        roots[x] = find_root(roots[x])
        return roots[x]
def unite(x, y):
    x = find_root(x)
    y = find_root(y)
    if (x==y):
        return
    if roots[x] > roots[y]:
        c, d = y,x
        x,y = c,d
    roots[x] += roots[y]
    roots[y] = x

for i in range(m):
    line = sys.stdin.readline().strip()
    a,b = map(int, line.split())
    c, d = a-1,b-1
    linked[c] += 1 
    linked[d] += 1
    unite(c,d)
#print(roots)
blacks = [[]for i in range(n)]
for i in range(k):
    line = sys.stdin.readline().strip()
    a,b = map(int, line.split())
    c,d = a-1, b-1
    blacks[c].append(d)
    blacks[d].append(c)
res = []
for i in range(n):
    r = -roots[find_root(i)] - 1 - linked[i]
    for one in blacks[i]:
        if find_root(one) == find_root(i):
            r -= 1
    res.append(r)
    
print (" ".join(map(str, res)))

Verdicts: Wrong Answer

Accepted
Problem: An SNS has N users - User 1, User 2, \cdots, User N.  Between these N users, there are some relationships - M _friendships_ and K _blockships_.  For each i = 1, 2, \cdots, M, there is a bidirectional friendship between User A_i and User B_i.  For each i = 1, 2, \cdots, K, there is a bidirectional blockship between User C_i and User D_i.  We define User a to be a _friend candidate_ for User b when all of the following four conditions are satisfied:    * a \neq b.   * There is not a friendship between User a and User b.   * There is not a blockship between User a and User b.   * There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a, c_L = b, and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1.  For each user i = 1, 2, ... N, how many friend candidates does it have?

Submission attempts (in order):
import sys
sys.getrecursionlimit(10**6)

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

par = [i for i in range(N+1)]


def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]


def bool_same(x,y):
    return root(x) == root(y)


def unite(x,y):
    x = root(x)
    y = root(y)
    if x != y:
        par[x] = y

AB = [list(map(int,input().split())) for i in range(M)]
CD = [list(map(int,input().split())) for i in range(K)]

for i in range(M):
    a,b = AB[i]
    unite(a,b)

member = [0 for i in range(N+1)]

for i in range(1,N+1):
    member[root(i)] += 1

ans = [member[par[i]]-1 for i in range(N+1)]

for i in range(M):
    a,b = AB[i]
    if bool_same(a,b):
        ans[a] -= 1
        ans[b] -= 1

for i in range(K):
    c,d = CD[i]
    if bool_same(c,d):
        ans[c] -= 1
        ans[d] -= 1

print(*ans[1:])


import sys
sys.setrecursionlimit(10**6)

N,M,K = map(int,input().split())
 
par = [i for i in range(N+1)]
 

def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]
 

def bool_same(x,y):
    return root(x) == root(y)
 

def unite(x,y):
    x = root(x)
    y = root(y)
    if x != y:
        par[x] = y
 
AB = [list(map(int,input().split())) for i in range(M)]
CD = [list(map(int,input().split())) for i in range(K)]
 
for a,b in AB:
    unite(a,b)
 
for i in range(N+1):
    root(i)
 
member = [0 for i in range(N+1)]
 
for p in par:
    member[p] += 1
 
ans = [member[par[i]]-1 for i in range(N+1)]
 
for a,b in AB:
    if bool_same(a,b):
        ans[a] -= 1
        ans[b] -= 1
for c,d in CD:
    if bool_same(c,d):
        ans[c] -= 1
        ans[d] -= 1
print(' '.join(map(str,ans[1:])))
 

Verdicts: Runtime Error

Accepted
Problem: An SNS has N users - User 1, User 2, \cdots, User N.  Between these N users, there are some relationships - M _friendships_ and K _blockships_.  For each i = 1, 2, \cdots, M, there is a bidirectional friendship between User A_i and User B_i.  For each i = 1, 2, \cdots, K, there is a bidirectional blockship between User C_i and User D_i.  We define User a to be a _friend candidate_ for User b when all of the following four conditions are satisfied:    * a \neq b.   * There is not a friendship between User a and User b.   * There is not a blockship between User a and User b.   * There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a, c_L = b, and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1.  For each user i = 1, 2, ... N, how many friend candidates does it have?

Submission attempts (in order):
import sys
sys.setrecursionlimit(10**6)
from collections import Counter

def dfs(nw):
    for nx in B[nw]:
        if V[nx]==-1:
            V[nx] = cnt
            dfs(nx)

F = [[] for _ in range(n)]
B = [[] for _ in range(n)]
n, m, k = list(map(int, sys.stdin.readaline().split()))
for i in range(m):
    a,b = map(lambda x: int(x)-1, map(int, sys.stdin.readline().split()))
    F[a].append(b)
    F[b].append(a)
for i in range(k):
    c,d = map(lambda x: int(x)-1, map(int, sys.stdin.readline().split()))
    F[c].append(d)
    F[d].append(c)

V = [-1]*n
cnt = 1
for i in range(n):
    if V[i]==-1:
        V[i] = cnt
        dfs(i)
        cnt += 1
cV = Counter(V)
ans = []
for i in range(n):
    ans.append(cV[V[i]]-1 - len(F[i]) - sum([V[b]==V[i] for b in B[i]]))

print(*ans)

import sys
sys.setrecursionlimit(10**6)
from collections import Counter

def dfs(nw):
    for nx in F[nw]:
        if V[nx]==-1:
            V[nx] = cnt
            dfs(nx)

n, m, k = list(map(int, sys.stdin.readline().split()))
F = [[] for _ in range(n)]
B = [[] for _ in range(n)]
for i in range(m):
    a,b = map(lambda x: int(x)-1, map(int, sys.stdin.readline().split()))
    F[a].append(b)
    F[b].append(a)
for i in range(k):
    c,d = map(lambda x: int(x)-1, map(int, sys.stdin.readline().split()))
    B[c].append(d)
    B[d].append(c)

V = [-1]*n
cnt = 1
for i in range(n):
    if V[i]==-1:
        V[i] = cnt
        dfs(i)
        cnt += 1
cV = Counter(V)
ans = []
for i in range(n):
    ans.append(cV[V[i]]-1 - len(F[i]) - sum([V[b]==V[i] for b in B[i]]))

print(*ans)

Verdicts: Runtime Error

Accepted
Problem: An SNS has N users - User 1, User 2, \cdots, User N.  Between these N users, there are some relationships - M _friendships_ and K _blockships_.  For each i = 1, 2, \cdots, M, there is a bidirectional friendship between User A_i and User B_i.  For each i = 1, 2, \cdots, K, there is a bidirectional blockship between User C_i and User D_i.  We define User a to be a _friend candidate_ for User b when all of the following four conditions are satisfied:    * a \neq b.   * There is not a friendship between User a and User b.   * There is not a blockship between User a and User b.   * There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a, c_L = b, and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1.  For each user i = 1, 2, ... N, how many friend candidates does it have?

Submission attempts (in order):


import sys
readline = sys.stdin.readine

N, M, K = map(int, readline().split())

F = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, readline().split())
    F[a].append(b)
    F[b].append(a)

B = [[] for _ in range(N + 1)]
for _ in range(K):
    c, d = map(int, readline().split())
    B[c].append(d)
    B[d].append(c)

seen = [-1] * (N + 1)
group = 0


def dfs(graph, s):
    stack = [s]
    seen[s] = group
    n_connection = 1

    while stack:
        u = stack.pop()
        for v in graph[u]:
            if seen[v] == -1:
                n_connection += 1
                seen[v] = group
                stack.append(v)

    return n_connection


union = {}
for i in range(1, N + 1):
    if seen[i] == -1:
        n = dfs(F, i)
        union[group] = n
        group += 1

ans = []
for i in range(1, N + 1):
    tmp = 0
    tmp += union[seen[i]] - 1
    tmp -= len(F[i])
    for j in B[i]:
        if seen[j] == seen[i]:
            tmp -= 1
    ans.append(tmp)

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




import sys
readline = sys.stdin.readline

N, M, K = map(int, readline().split())

F = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, readline().split())
    F[a].append(b)
    F[b].append(a)

B = [[] for _ in range(N + 1)]
for _ in range(K):
    c, d = map(int, readline().split())
    B[c].append(d)
    B[d].append(c)

seen = [-1] * (N + 1)
group = 0


def dfs(graph, s):
    stack = [s]
    seen[s] = group
    n_connection = 1

    while stack:
        u = stack.pop()
        for v in graph[u]:
            if seen[v] == -1:
                n_connection += 1
                seen[v] = group
                stack.append(v)

    return n_connection


union = {}
for i in range(1, N + 1):
    if seen[i] == -1:
        n = dfs(F, i)
        union[group] = n
        group += 1

ans = []
for i in range(1, N + 1):
    tmp = 0
    tmp += union[seen[i]] - 1
    tmp -= len(F[i])
    for j in B[i]:
        if seen[j] == seen[i]:
            tmp -= 1
    ans.append(tmp)

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


Verdicts: Runtime Error

Accepted
Problem: An SNS has N users - User 1, User 2, \cdots, User N.  Between these N users, there are some relationships - M _friendships_ and K _blockships_.  For each i = 1, 2, \cdots, M, there is a bidirectional friendship between User A_i and User B_i.  For each i = 1, 2, \cdots, K, there is a bidirectional blockship between User C_i and User D_i.  We define User a to be a _friend candidate_ for User b when all of the following four conditions are satisfied:    * a \neq b.   * There is not a friendship between User a and User b.   * There is not a blockship between User a and User b.   * There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a, c_L = b, and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1.  For each user i = 1, 2, ... N, how many friend candidates does it have?

Submission attempts (in order):
import sys
sys.setrecursionlimit(10*9)

n,m,k = map(int,input().split())
parent_of = [-1 for _ in range(n)]
#print(parent_of)
def root_of(x):
	if parent_of[x] < 0:
		return x
	else:
		parent_of[x] = root_of(parent_of[x])
		return parent_of[x]

def unite(x,y):
	top_root_x = root_of(x)
	top_root_y = root_of(y)
	if top_root_x == top_root_y:
		return False
	if parent_of[top_root_x] > parent_of[top_root_y]:
		top_root_x,top_root_y = top_root_y,top_root_x
	#print(parent_of[top_root_y])
	parent_of[top_root_x] += parent_of[top_root_y]
	parent_of[top_root_y] = top_root_x
	return True

def size_of(x):
		return -parent_of[root_of(x)]

def is_same(x,y):
	return root_of(x) == root_of(y)

friend_list = [-1] * n
for _ in range(m):
	a,b = map(int,input().split())
	a -= 1
	b -= 1
	friend_list[a] -=1
	friend_list[b] -=1
	unite(a,b)

for _ in range(k):
	c,d = map(int,input().split())
	c -= 1
	d -= 1
	if root_of(c) == root_of(d):
		block_list[c] -= 1
		block_list[d] -= 1
for i in range(n):
	friend_list[i] += size_of(i)
	#print(size_of(i))
print(*friend_list)


import sys
sys.setrecursionlimit(10*9)

n,m,k = map(int,input().split())
parent_of = [-1 for _ in range(n)]
#print(parent_of)
def root_of(x):
	if parent_of[x] < 0:
		return x
	else:
		parent_of[x] = root_of(parent_of[x])
		return parent_of[x]

def unite(x,y):
	top_root_x = root_of(x)
	top_root_y = root_of(y)
	if top_root_x == top_root_y:
		return False
	if parent_of[top_root_x] > parent_of[top_root_y]:
		top_root_x,top_root_y = top_root_y,top_root_x
	#print(parent_of[top_root_y])
	parent_of[top_root_x] += parent_of[top_root_y]
	parent_of[top_root_y] = top_root_x
	return True

def size_of(x):
		return -parent_of[root_of(x)]

def is_same(x,y):
	return root_of(x) == root_of(y)

friend_list = [-1] * n
for _ in range(m):
	a,b = map(int,input().split())
	a -= 1
	b -= 1
	friend_list[a] -=1
	friend_list[b] -=1
	unite(a,b)

for _ in range(k):
	c,d = map(int,input().split())
	c -= 1
	d -= 1
	if root_of(c) == root_of(d):
		friend_list[c] -= 1
		friend_list[d] -= 1
for i in range(n):
	friend_list[i] += size_of(i)
	#print(size_of(i))
print(*friend_list)


Verdicts: Runtime Error

Accepted
Problem: An SNS has N users - User 1, User 2, \cdots, User N.  Between these N users, there are some relationships - M _friendships_ and K _blockships_.  For each i = 1, 2, \cdots, M, there is a bidirectional friendship between User A_i and User B_i.  For each i = 1, 2, \cdots, K, there is a bidirectional blockship between User C_i and User D_i.  We define User a to be a _friend candidate_ for User b when all of the following four conditions are satisfied:    * a \neq b.   * There is not a friendship between User a and User b.   * There is not a blockship between User a and User b.   * There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a, c_L = b, and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1.  For each user i = 1, 2, ... N, how many friend candidates does it have?

Submission attempts (in order):
from collections import deque
N, M, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]

F = [[[] for _ in range(2)] for _ in range(N)]
for m in AB:
    F[m[0] - 1][0].append(m[1] - 1)
    F[m[1] - 1][0].append(m[0] - 1)
for k in CD:
    F[k[0] - 1][1].append(k[1] - 1)
    F[k[1] - 1][1].append(k[0] - 1)

L = [0] * N
m = [[] for _ in range(N)]

for i in range(N):
    if L[i] != 0:
        continue
    l = []
    c = 0
    d = [0] * N
    d[i] = 1
    l.append(i)
    Q = deque()
    Q.append(i)
    while len(Q) > 0:
        q = Q.pop()
        for j in range(len(F[q][0])):
            a = F[q][0][j]
            if d[a] == 1:
                continue
            d[a] = 1
            c += 1
            Q.append(a)
            l.append(a)
    m[i] = l
    for j in l:
        L[j] = c
        m[j] = l

for i in range(N):
    print(L[i] - len(F[i][0]) - len(set(F[i][1]) & set(m[i])), end=' ')

print('')

import time
from collections import deque
N, M, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]

F = [set() for _ in range(N)]
B = [set() for _ in range(N)]

for i, j in AB:
    F[i - 1].add(j - 1)
    F[j - 1].add(i - 1)
for i, j in CD:
    B[i - 1].add(j - 1)
    B[j - 1].add(i - 1)

Q = deque()
S = [0] * N
d = [0] * N

for i in range(N):
    if d[i] != 0:
        continue
    L = {i}
    d[i] = 1
    Q.append(i)
    while len(Q) > 0:
        q = Q.pop()
        for j in F[q]:
            if d[j] == 0:
                d[j] = 1
                Q.append(j)
                L.add(j)
    for k in L:
        S[k] = len(L) - len(L & F[k]) - len(L & B[k]) - 1

print(*S)


Verdicts: Time Limit Exceeded

Accepted
Problem: An SNS has N users - User 1, User 2, \cdots, User N.  Between these N users, there are some relationships - M _friendships_ and K _blockships_.  For each i = 1, 2, \cdots, M, there is a bidirectional friendship between User A_i and User B_i.  For each i = 1, 2, \cdots, K, there is a bidirectional blockship between User C_i and User D_i.  We define User a to be a _friend candidate_ for User b when all of the following four conditions are satisfied:    * a \neq b.   * There is not a friendship between User a and User b.   * There is not a blockship between User a and User b.   * There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a, c_L = b, and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1.  For each user i = 1, 2, ... N, how many friend candidates does it have?

Submission attempts (in order):
import sys
input = sys.stdin.readline

def main():
    N, M, K = map(int, input().split())

    friends = [[False] * N for _ in range(N)]
    print(friends)

    for _ in range(M):
        A, B = map(int,input().split())
        friends[A-1][B-1] = True
        friends[B-1][A-1] = True

    print(friends)
    

if __name__ == "__main__":
    main()


import sys
from collections import deque
input = sys.stdin.readline

class UnionFind(object):
    def __init__(self, N):
        
        self.node = [-1] * N

    def root(self, x):
        if self.node[x] < 0:
            
            return x
        else:
            
            self.node[x] = self.root(self.node[x])
            
            return self.node[x]

    def size(self, x):
        
        
        return -self.node[self.root(x)]

    def connect(self, x, y):
        a = self.root(x)  
        b = self.root(y)  

        
        if a == b:
            return

        
        if self.size(a) < self.size(b):
            a, b = b, a

        
        self.node[a] += self.node[b]
        
        self.node[b] = a

        return

    def show_nodes(self):
        return self.node


def main():
    N, M, K = map(int, input().split())

    tree = UnionFind(N)

    friends = [ list(map(int, input().split())) for _ in range(M)]

    for A, B in friends:
        tree.connect(A-1, B-1)

    ans = [tree.size(x) - 1 for x in range(N)]

    for A, B in friends:
        if tree.root(A-1) == tree.root(B-1):
            ans[A-1] -= 1
            ans[B-1] -= 1

    for _ in range(K):
        C, D = map(int,input().split())
        if tree.root(C - 1) == tree.root(D - 1):
            ans[C-1] -= 1
            ans[D-1] -= 1

    print(*ans)


if __name__ == "__main__":
    main()


Verdicts: Wrong Answer

Accepted
Problem: You are given a string S of length N consisting of lowercase English letters.  Process Q queries of the following two types:    * Type 1: change the i_q-th character of S to c_q. (Do nothing if the i_q-th character is already c_q.)   * Type 2: answer the number of different characters occurring in the substring of S between the l_q-th and r_q-th characters (inclusive).

Submission attempts (in order):
import bisect
N=input()
S=list(input())
alphabet=[[] for _ in range(26)]
for i,s in enumerate(S):
    alphabet[ord(s)-ord('a')].append(i)
Q=int(input())
for _ in range(Q):
    Type,A,B=input().split()
    if Type=="1":
        A=int(A)
        s=S[A-1]
        if s==B:
            continue
        o=ord(s)-ord("a")
        alphabet[o].pop(bisect.bisect_left(alphabet[o],A-1))
        index=bisect.bisect(alphabet[B-1],A-1)
        alphabet[B-1].insert(index,A-1)
        S[A-1]=B
    else:
        A=int(A)
        B=int(B)
        ans=0
        for i in range(26):
            indexL=bisect.bisect_left(alphabet[i],A-1)
            
            #ans+=(indexL!=indexR)
            if indexL==len(alphabet[i]):
                continue
            ans+=(alphabet[i][indexL]<=B-1)
        print(ans)


import bisect
N=input()
S=list(input())
alphabet=[[] for _ in range(26)]
for i,s in enumerate(S):
    alphabet[ord(s)-ord('a')].append(i)
Q=int(input())
for _ in range(Q):
    Type,A,B=input().split()
    if Type=="1":
        A=int(A)
        s=S[A-1]
        if s==B:
            continue
        o=ord(s)-ord("a")
        alphabet[o].pop(bisect.bisect_left(alphabet[o],A-1))
        index=bisect.bisect(alphabet[o],A-1)
        
        
        alphabet[B-1].insert(index,A-1)
        S[A-1]=B
    else:
        A=int(A)
        B=int(B)
        ans=0
        for i in range(26):
            indexL=bisect.bisect_left(alphabet[i],A-1)
            
            #ans+=(indexL!=indexR)
            if indexL==len(alphabet[i]):
                continue
            ans+=(alphabet[i][indexL]<=B-1)
        print(ans)


import bisect
N=input()
S=list(input())
alphabet=[[] for _ in range(26)]
for i,s in enumerate(S):
    alphabet[ord(s)-ord('a')].append(i)
Q=int(input())
for _ in range(Q):
    Type,A,B=input().split()
    if Type=="1":
        A=int(A)
        s=S[A-1]
        if s==B:
            continue
        o=ord(s)-ord("a")
        alphabet[o].pop(bisect.bisect_left(alphabet[o],A-1))
        index=bisect.bisect(alphabet[ord(B)-ord("a")],A-1)
        alphabet[ord(B)-ord("a")].insert(index,A-1)
        S[A-1]=B
    else:
        A=int(A)
        B=int(B)
        ans=0
        for i in range(26):
            indexL=bisect.bisect_left(alphabet[i],A-1)
            
            #ans+=(indexL!=indexR)
            if indexL==len(alphabet[i]):
                continue
            ans+=(alphabet[i][indexL]<=B-1)
        print(ans)


Verdicts: Runtime Error

Runtime Error

Accepted
Problem: You are given a string S of length N consisting of lowercase English letters.  Process Q queries of the following two types:    * Type 1: change the i_q-th character of S to c_q. (Do nothing if the i_q-th character is already c_q.)   * Type 2: answer the number of different characters occurring in the substring of S between the l_q-th and r_q-th characters (inclusive).

Submission attempts (in order):

# E - Simple String Queries

from bisect import bisect_left, insort_left
import sys
input = sys.stdin.readline
OFS = ord('a')
_ = input()
S = list(input()[:-1])

D = [[] for _ in [0]*26]
for i, s in enumerate(S):
    D[s].append(i)

for _ in [0]*int(input()):
    Q = input()[:-1].split()
    if Q[0] == '1':
        i, c = int(Q[1])-1, Q[2]

        D[s].pop(bisect_left(D[S[i]], i))
        insort_left(D[ord(c)-OFS], i)
        S[i] = c

    else:
        l, r = int(Q[1])-1, int(Q[2])-1

        cnt = 0
        for L in D:
            i = bisect_left(L, l)
            if i < len(L) and L[i] <= r:
                cnt += 1

        print(cnt)



# E - Simple String Queries

from bisect import bisect_left, insort_left
import sys
input = sys.stdin.readline
OFS = ord('a')
_ = input()
S = list(input()[:-1])

D = [[] for _ in [0]*26]
for i, s in enumerate(S):
    D[ord(s)-OFS].append(i)

for _ in [0]*int(input()):
    Q = input()[:-1].split()
    if Q[0] == '1':
        i, c = int(Q[1])-1, Q[2]

        if S[i] != c:
            s = ord(S[i])-OFS
            D[s].pop(bisect_left(D[s], i))
            insort_left(D[ord(c)-OFS], i)
            S[i] = c

    else:
        l, r = int(Q[1])-1, int(Q[2])-1

        cnt = 0
        for L in D:
            i = bisect_left(L, l)
            if i < len(L) and L[i] <= r:
                cnt += 1

        print(cnt)


Verdicts: Runtime Error

Accepted
Problem: You are given a string S of length N consisting of lowercase English letters.  Process Q queries of the following two types:    * Type 1: change the i_q-th character of S to c_q. (Do nothing if the i_q-th character is already c_q.)   * Type 2: answer the number of different characters occurring in the substring of S between the l_q-th and r_q-th characters (inclusive).

Submission attempts (in order):
from bisect import bisect_left,bisect
n = int(input())
s = list(input())
q = int(input())
al=[[] for i in range(26)]
for i in range(n):
    al[ord(s[i])-ord("a")].append(i)

for i in range(q):
    a , b , x = input().split()
    if a == "1":
        al[ord(s[int(b)-1])-ord("a")].pop(al[ord(s[int(b)-1])-ord("a")],int(b)-1)
        al[ord(x)-ord("a")].insert(bisect_left(al[ord(x)-ord("a")],int(b)-1),int(b)-1)
        s[int(b)-1] = x
    elif a == "2":
        b = int(b)-1
        x = int(x)-1
        cou = 0
        for j in range(26):
            l = bisect_left(al[j],b)
            r = bisect(al[j],x)
            if l != r:
                cou += 1
        print(cou)


def main():
    from bisect import bisect_left,bisect
    n = int(input())
    s = list(input())
    q = int(input())
    al=[[] for i in range(26)]
    for i in range(n):
        al[ord(s[i])-97].append(i)
    ans = []
    for i in range(q):
        a , b , x = input().split()
        if a == "1":
            al[ord(s[int(b)-1])-97].pop(bisect_left(al[ord(s[int(b)-1])-97],int(b)-1))
            al[ord(x)-97].insert(bisect_left(al[ord(x)-97],int(b)-1),int(b)-1)
            s[int(b)-1] = x
        elif a == "2":
            b = int(b)-1
            x = int(x)-1
            cou = 0
            for j in range(26):
                l = bisect_left(al[j],b)
                r = bisect(al[j],x)
                if l != r:
                    cou += 1
            ans.append(cou)
    for i in ans:
        print(i)

if __name__ == '__main__':
    main()

Verdicts: Runtime Error

Accepted
Problem: You are given a string S of length N consisting of lowercase English letters.  Process Q queries of the following two types:    * Type 1: change the i_q-th character of S to c_q. (Do nothing if the i_q-th character is already c_q.)   * Type 2: answer the number of different characters occurring in the substring of S between the l_q-th and r_q-th characters (inclusive).

Submission attempts (in order):
import math

n = int(input())
s = input()
S = [ord(i) - 97 for i in s]
q = int(input())
HEIGHT = math.ceil(math.log(n) / math.log(2))
SIZE = 1 << HEIGHT

def build_tree_for_letter(letter):
    tree = [False for _ in range(2 << HEIGHT)]
    for i in range(1 << HEIGHT):
        tree[i + (1 << HEIGHT)] = True if i < n and s[i] == chr(97 + letter) else False

    for i in range(HEIGHT - 1, -1, -1):
        for x in range(1<<i, 2<<i):
            tree[x] = any((tree[x<<1], tree[(x<<1)+1]))

    return tree


def build():
    return [build_tree_for_letter(letter) for letter in range(26)]



def update(x, letter, positive=True):
    trees[letter][x] = (positive == True)
    while x > 1:
        x >>= 1
        trees[letter][x] = any((trees[letter][x << 1], trees[letter][(x << 1) + 1]))


def query(ll, rr):

    # print("query: ", l, r)
    total = 0
    for letter in range(26):
        l, r = ll, rr
        is_letter = False
        while l < r:
            if l%(2) != 0:
                is_letter = any((is_letter, trees[letter][l]))
                l += 1
            l >>= 1
            if r%(2) != 0:
                r -= 1
                is_letter = any((is_letter, trees[letter][r]))
            r >>= 1
        total += is_letter
    return total



trees = build()

for i in range(q):
    a, b, c = input().split()
    b = int(b) - 1 + SIZE
    if int(a) == 1:
        c = ord(c) - 97
        update(b, S[b], positive=False)
        S[b] = c
        update(b, c, positive=True)
    else:
        print(query(b, int(c)+SIZE))








import math

n = int(input())
s = input()
S = [ord(i) - 97 for i in s]
q = int(input())
HEIGHT = math.ceil(math.log(n) / math.log(2))
SIZE = 1 << HEIGHT

def build_tree():
    tree = [0 for _ in range(SIZE<<1)]

    for i, letter in enumerate(s):
        tree[i+SIZE] = 1<<(ord(letter)-97)

    for i in range(HEIGHT - 1, -1, -1):
        for x in range(1<<i, 2<<i):
            tree[x] = tree[x<<1] | tree[(x<<1)+1]

    return tree




def update(x, number):
    tree[x] = number
    while x > 1:
        x >>= 1
        tree[x] = tree[x << 1] | tree[(x << 1) + 1]


def query(l, r):
    total = 0
    while l < r:
        if l&1:
            total |= tree[l]
            l += 1
        l >>= 1
        if r&1:
            r -= 1
            total |= tree[r]
        r >>= 1
    return bin(total).count('1')



tree = build_tree()

for i in range(q):
    a, b, c = input().split()
    b = int(b) - 1
    if int(a) == 1:
        update(b + SIZE, S[b])
        c = 1 << (ord(c) - 97)
        S[b] = c
        update(b + SIZE, c)
    else:
        print(query(b + SIZE, int(c)+SIZE))








Verdicts: Runtime Error

Accepted
Problem: You are given a string S of length N consisting of lowercase English letters.  Process Q queries of the following two types:    * Type 1: change the i_q-th character of S to c_q. (Do nothing if the i_q-th character is already c_q.)   * Type 2: answer the number of different characters occurring in the substring of S between the l_q-th and r_q-th characters (inclusive).

Submission attempts (in order):
import bisect

n = int(input())
s = list(input())
q = int(input())
l = [[] for i in range(26)]
for i in range(n):
    l[ord(s[i])-ord("a")].append(i)
print(l)

for i in range(q):
    x,y,z = input().split()
    if int(x) == 1:
        if s[int(y)-1] == z:
            continue
        index = bisect.bisect_left(l[ord(s[int(y)-1])-ord("a")],int(y)-1)
        l[ord(s[int(y)-1])-ord("a")].pop(index)
        index = bisect.bisect_left(l[ord(z)-ord("a")],int(y)-1)
        l[ord(z)-ord("a")].insert(index,int(y)-1)
    if int(x) == 2:
        count = 0
        for j in l:
            index = bisect.bisect_left(j,int(y)-1)
            if index < len(j) and j[index] < int(z):
                count += 1
        print(count)





from bisect import bisect_left as bl

n = int(input())
s = list(input())
q = int(input())
l = [[] for i in range(26)]
for i in range(n):
    l[ord(s[i])-ord("a")].append(i)
for i in range(q):
    x,y,z = input().split()
    if x == "1":
        y = int(y)-1
        if s[y] == z:
            continue
        b = ord(s[y])-ord("a")
        a = ord(z)-ord("a")
        l[b].pop(bl(l[b],y))
        l[a].insert(bl(l[a],y),y)
        s[y] = z
    if x == "2":
        count = 0
        for j in l:
            index = bl(j,int(y)-1)
            if index < len(j) and j[index] < int(z):
                count += 1
        print(count)

Verdicts: Runtime Error

Accepted
Problem: You are given a string S of length N consisting of lowercase English letters.  Process Q queries of the following two types:    * Type 1: change the i_q-th character of S to c_q. (Do nothing if the i_q-th character is already c_q.)   * Type 2: answer the number of different characters occurring in the substring of S between the l_q-th and r_q-th characters (inclusive).

Submission attempts (in order):
n = int(input())
s = input()

x = [[0 for _i in range(n)] for _j in range(26)]
for i in range(n):
    x[ord(s[i])-97][i] = 1
q = int(input())
r = []
for _i in range(q):
    y = list(input().split())
    i = int(y[1])-1
    if y[0] == "1":
        x[ord(s[i])-97][i] = 0
        x[ord(y[2])-97][i] = 1
    else:
        c = 0
        for j in range(26):
            if 1 in x[j][i:int(y[2])]:
                c += 1
        r.append(c)
print(*r)

n = int(input())
s = list(input())
s = [ord(i)-97 for i in s]

dic = {}
for i in range(26):
    dic[i] = []

for i in range(n):
    dic[s[i]].append(i)

for i in range(26):
    dic[i].append(float('inf'))

from bisect import bisect_left
q = int(input())
for i in range(q):
    x, y, z = input().split()
    if x == '1':
        y, z = int(y) - 1, ord(z) - 97
        p = bisect_left(dic[s[y]], y)
        dic[s[y]].pop(p)
        dic[z].insert(bisect_left(dic[z], y), y)
        s[y] = z
    else:
        res = 0
        y, z = int(y) - 1, int(z) - 1
        for i in range(26):
            p = dic[i][bisect_left(dic[i], y)]
            if p <= z:
                res += 1
        print(res)

Verdicts: Wrong Answer

Accepted
Problem: You are given a string S of length N consisting of lowercase English letters.  Process Q queries of the following two types:    * Type 1: change the i_q-th character of S to c_q. (Do nothing if the i_q-th character is already c_q.)   * Type 2: answer the number of different characters occurring in the substring of S between the l_q-th and r_q-th characters (inclusive).

Submission attempts (in order):
n=int(input())+1
w = input()
data=[0]*n*2
def update(i,x):
    i+=n
    data[i]=x
    i//=2
    while i:
      data[i]=data[i*2]|data[i*2+1]
      i//=2
def query(l,r):
    l+=n
    r+=n
    s=0
    while l<r:
      if l&1 == 1:
        s|=data[l]
        l+=1
      if r&1 == 1:
        r-=1
        s|=data[r]
      l//=2
      r//=2
    return bin(s).count('1')
def word_num(a):
    return 1<<(ord(a)-97)

for i in range(n-1):
    data[i+n] = word_num(w[i])    
for i in range(n-1,0,-1):
    data[i]=data[i*2]|data[i*2 + 1]
print(list(map(lambda x:bin(x),data)))      

ans=[]
q=int(input())
for i in range(q):
    a,s,t=input().split()
    if a=='1':
        s=int(s)
        update(int(s)-1,word_num(t))
    if a=='2':
        s=int(s)
        t=int(t)
        ans.append(query(int(s)-1,int(t)))
for i in range(len(ans)):
    print(ans[i])


n=int(input())+1
w = input()
data=[0]*n*2
def update(i,x):
    i+=n
    data[i]=x
    i//=2
    while i:
      data[i]=data[i*2]|data[i*2+1]
      i//=2
def query(l,r):
    l+=n
    r+=n
    s=0
    while l<r:
      if l&1 == 1:
        s|=data[l]
        l+=1
      if r&1 == 1:
        r-=1
        s|=data[r]
      l//=2
      r//=2
    return bin(s).count('1')
def word_num(a):
    return 1<<(ord(a)-97)

for i in range(n-1):
    data[i+n] = word_num(w[i])    
for i in range(n-1,0,-1):
    data[i]=data[i*2]|data[i*2 + 1]

ans=[]
q=int(input())
for i in range(q):
    a,s,t=input().split()
    if a=='1':
        s=int(s)
        update(int(s)-1,word_num(t))
    if a=='2':
        s=int(s)
        t=int(t)
        ans.append(query(int(s)-1,int(t)))
for i in range(len(ans)):
    print(ans[i])

Verdicts: Wrong Answer

Accepted
Problem: You are given a string S of length N consisting of lowercase English letters.  Process Q queries of the following two types:    * Type 1: change the i_q-th character of S to c_q. (Do nothing if the i_q-th character is already c_q.)   * Type 2: answer the number of different characters occurring in the substring of S between the l_q-th and r_q-th characters (inclusive).

Submission attempts (in order):
N = int(input())
S = input()
Q = int(input())
Query = [input() for _ in range(Q)]
dic = {chr(i+ord("a")):[] for i in range(26)}
for i, s in enumerate(S):
    dic[s].append(i)
for q in Query:
    t,a,b = q.split()
    if(t == "1"):
        a_index = int(a)-1
        if(S[a_index]==b):
            continue
        tmp_index = bisect_left(dic[S[a_index]],a_index)
        dic[s[a]].pop(tmp_index)
        insort.left(dic[b],a)
        s[a] = b
    elif(t == "2"):
        a_index = int(a)-1
        b_index = int(b)-1
        cnt = 0
        for li in dic.values():
            if(li and a_index <= li[-1] and li[bisect_left(li,a_index)] <= b_index):
                    cnt += 1
        print(cnt)

from bisect import insort_left, bisect_left
N = int(input())
S = list(input())
Q = int(input())
Query = [input() for _ in range(Q)]
dic = {chr(i+ord("a")):[] for i in range(26)}
for i, s in enumerate(S):
    dic[s].append(i)
for q in Query:
    t,a,b = q.split()
    a = int(a)-1
    if(t == "1"):
        if(S[a]==b):
            continue
        tmp_index = bisect_left(dic[S[a]],a)
        dic[S[a]].pop(tmp_index)
        insort_left(dic[b],a)
        S[a] = b
    elif(t == "2"):
        b = int(b)-1
        cnt = 0
        for li in dic.values():
            if li and a<=li[-1] and li[bisect_left(li, a)] <= b:
                cnt += 1
        print(cnt)

Verdicts: Runtime Error

Accepted
Problem: You are given a string S of length N consisting of lowercase English letters.  Process Q queries of the following two types:    * Type 1: change the i_q-th character of S to c_q. (Do nothing if the i_q-th character is already c_q.)   * Type 2: answer the number of different characters occurring in the substring of S between the l_q-th and r_q-th characters (inclusive).

Submission attempts (in order):
import bisect

n = int(input())
s = input()
q = int(input())

alpha_map = {i:[] for i in alpha}
for i,c in enumerate(s):
    bisect.insort(alpha_map[c],i+1)
    
for _ in range(q):
    x,y,z = map(str,input().split())
    if int(x) == 1:
        y = int(y)
        bef = s[y-1]
        if bef == z:
            continue
        alpha_map[bef].pop(bisect.bisect_left(alpha_map[bef],y))
        bisect.insort(alpha_map[z],y)
        s = s[:y-1]+z+s[y:]
    else:
        count = 0
        for i,j in alpha_map.items():
            idx = bisect.bisect_left(j,int(y))
            if idx < len(j) and j[idx] <= int(z):
                    count += 1
        print(count)

import bisect

n = int(input())
s = list(input())
q = int(input())

alpha_map = {chr(i):[] for i in range(97,123)}
for i,c in enumerate(s):
    bisect.insort(alpha_map[c],i+1)
    
for _ in range(q):
    x,y,z = map(str,input().split())
    if int(x) == 1:
        y = int(y)
        bef = s[y-1]
        if bef == z:
            continue
        alpha_map[bef].pop(bisect.bisect_left(alpha_map[bef],y))
        bisect.insort(alpha_map[z],y)
        s[y-1] = z
    else:
        count = 0
        for i,j in alpha_map.items():
            idx = bisect.bisect_left(j,int(y))
            if idx < len(j) and j[idx] <= int(z):
                    count += 1
        print(count)

Verdicts: Runtime Error

Accepted
Problem: You are given a string S of length N consisting of lowercase English letters.  Process Q queries of the following two types:    * Type 1: change the i_q-th character of S to c_q. (Do nothing if the i_q-th character is already c_q.)   * Type 2: answer the number of different characters occurring in the substring of S between the l_q-th and r_q-th characters (inclusive).

Submission attempts (in order):
from bisect import bisect_left,bisect_right
import string 

dic = {c:[] for c in string.ascii_lowercase}

n = int(input())
s = list(input())
q = int(input())

for i,c in enumerate(s,start=1):
  dic[c].append(i)
print(dic)

for i in range(q):
  p,l,r = map(str,input().split())
  if p =='1':
    j = int(l)
    if r == s[j-1]:
      continue
    c = s[j-1]    
    dic[c].pop(bisect_left(dic[c],j))
    dic[r].insert(bisect_left(dic[r],j),j)
    s[j-1] = r
  else:
    ans = 0
    l = int(l)
    r = int(r)
    for c in string.ascii_lowercase:
      pl = bisect_left(dic[c],l)
      if pl < len(dic[c]):
        if dic[c][pl] <= r:
          ans += 1
    print(ans)


from bisect import bisect_left
import string 

dic={c:[] for c in string.ascii_lowercase}
N=int(input())
S=list(input())
Q=int(input())
for i in range(len(S)):
  dic[S[i]].append(i+1)

for i in range(Q):
  a,b,c=map(str,input().split())
  if a=='1':
    if S[int(b)-1]==c:
      continue
    b=int(b)
    f=S[b-1]
    d=bisect_left(dic[f],b)
    e=bisect_left(dic[c],b)
    dic[f].pop(d)
    dic[c].insert(e,b)
    S[b-1]=c
  else:
    ans=0
    b,c=int(b),int(c)
    for j in string.ascii_lowercase:
      d=bisect_left(dic[j],b)
      if d<len(dic[j]):
        if dic[j][d]<=c:
          ans+=1
    print(ans)


Verdicts: Wrong Answer

Accepted
Problem: You are given a string S of length N consisting of lowercase English letters.  Process Q queries of the following two types:    * Type 1: change the i_q-th character of S to c_q. (Do nothing if the i_q-th character is already c_q.)   * Type 2: answer the number of different characters occurring in the substring of S between the l_q-th and r_q-th characters (inclusive).

Submission attempts (in order):
n = int(input())
s = list(input())
q = int(input())
query = []
a = []
for _ in range(q):
    method, i, c = input().split()
    if method == "1":
        a.append([i, c])
    else:
        a.append([i, c])
        query.append(a)
        a = []
string = []
now = s
for qq in query:
    if len(qq) == 1:
        string.append(now)
        continue
    for i, c in qq[:-1]:
        i = int(i)
        now[i-1] = c
    string.append(now)

for qq, ss in zip(query, string):
    l, r = map(int, qq[-1])
    print(len(set(ss[l:r+1])))






class SegmentTree:

    def __init__(self, ls, ide, seg_func):
        n = len(ls)
        self.num = 2 ** (n - 1).bit_length()
        self.seg_func = seg_func
        self.ide = ide
        self.tree = [self.ide] * (2 * self.num - 1)
        for i, l in enumerate(ls):
            self.tree[i + self.num - 1] = l

        for i in range(self.num - 2, -1, -1):  
            self.tree[i] = seg_func(self.tree[2 * i + 1], self.tree[2 * i + 2])

    def update(self, i, x):
        i += self.num - 1
        self.tree[i] = x
        while i:
            i = (i-1)//2
            self.tree[i] = self.seg_func(self.tree[2 * i + 1], self.tree[2 * i + 2])

    def query(self, l, r):
        if r < l:
            return ValueError('invalid index')

        l += self.num - 1
        r += self.num - 2
        res = self.ide
        while r - l > 1:  
            if l & 1 == 0:
                res = self.seg_func(res, self.tree[l])
            if r & 1 == 1:
                res = self.seg_func(res, self.tree[r])
                r -= 1
            l = l // 2  
            r = (r - 1) // 2  
        if l == r:
            res = self.seg_func(res, self.tree[l])
        else:
            res = self.seg_func(res, self.tree[l])
            res = self.seg_func(res, self.tree[r])
        return res


def f(a, b):
    return a | b


n = int(input())
s = [1 << (ord(r) - ord("a")) for r in input()]
q = int(input())
st = SegmentTree(s, 0, f)

for _ in range(q):
    m, i, c = input().split()

    if int(m) - 1:
        x = st.query(int(i)-1, int(c))
        print(bin(x).count("1"))
    else:
        st.update(int(i)-1, 1 << (ord(c) - ord("a")))


Verdicts: Wrong Answer

Accepted