Problem:


Score : 600 points

Problem Statement

We have N colored balls arranged in a row from left to right; the color of the i-th ball from the left is c_i.

You are given Q queries. The i-th query is as follows: how many different colors do the l_i-th through r_i-th balls from the left have?

Constraints

1\leq N,Q \leq 5 \times 10^5

1\leq c_i \leq N

1\leq l_i \leq r_i \leq N

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
c_1 c_2 \cdots c_N
l_1 r_1
l_2 r_2
:
l_Q r_Q

Output

Print Q lines. The i-th line should contain the response to the i-th query.

Sample Input 1

4 3
1 2 1 3
1 3
2 4
3 3

Sample Output 1

2
3
1

The 1-st, 2-nd, and 3-rd balls from the left have the colors 1, 2, and 1 - two different colors.

The 2-st, 3-rd, and 4-th balls from the left have the colors 2, 1, and 3 - three different colors.

The 3-rd ball from the left has the color 1 - just one color.

Sample Input 2

10 10
2 5 6 5 2 1 7 9 7 2
5 5
2 4
6 7
2 2
7 8
7 9
1 8
6 9
8 10
6 8

Sample Output 2

1
2
2
1
2
2
6
3
3
3



Sample input:
4 3
1 2 1 3
1 3
2 4
3 3


Sample output:
2
3
1

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
 
 
class SegmentTree:
    def __init__(self, a):
        self.padding = 0
        self.n = len(a)
        self.N = 2 ** (self.n-1).bit_length()
        self.seg_data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n)
        for i in range(2*self.N-2, 0, -2):
            self.seg_data[(i-1)//2] = self.seg_data[i] + self.seg_data[i-1]
    
    def __len__(self):
        return self.n
    
    def update(self, i, x):
        idx = self.N - 1 + i
        self.seg_data[idx] = x
        while idx:
            idx = (idx-1) // 2
            self.seg_data[idx] = self.seg_data[2*idx+1] + self.seg_data[2*idx+2]
    
    def query(self, i, j):
        # [i, j)
        if i == j:
            return self.seg_data[self.N - 1 + i]
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j # 閉区間にする
            result = self.padding
            while idx1 < idx2 + 1:
                if idx1&1 == 0: # idx1が偶数
                    result = result + self.seg_data[idx1]
                if idx2&1 == 1: # idx2が奇数
                    result = result + self.seg_data[idx2]
                    idx2 -= 1
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            return result
    
    @property
    def data(self):
        return self.seg_data[self.N-1:self.N-1+self.n]
 
 
N, Q = map(int, readline().split())
C = list(map(int, readline().split()))
data = list(map(int,read().split()))
lr = [[i, data[2*i], data[2*i+1]] for i in range(0, Q)]
lr.sort(key=lambda x:x[2])

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
class BIT():
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
 
    def get_sum(self,i):
        s = 0
        while i:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i < self.size:
            self.tree[i] += x
            i += i & -i
 
n,q = map(int,readline().split())
c = list(map(int,readline().split()))
lr = list(map(int,read().split()))
it = iter(lr)
lr2 = []
for i,l,r in zip(range(q),it,it):
    lr2.append((r-1,l-1,i))
 
lr2.sort()

Submission status: Wrong Answer

Solution code:
n,q = map(int, input().split())
c = list(map(int, input().split()))
cl = [0]*n
for i in range(n):
  if cl[i]!=1:
    cl[i] += 1
def cumsum(a):
  s = [0]*n
  s[0] = a[0]
  for i in range(n-1):
    s[i+1] = a[i+1] + s[i]
  return s
print(cl)
for _ in range(q):
  l,r = map(int, input().split())
  print(len(set(c[l-1:r])))

Submission status: Wrong Answer

Solution code:
import math
N,Q=[int(r) for r in input().split()]
C=input().split()

for i in range(Q):
  a,b=[int(r) for r in input().split()]
  ans=C[a-1:b]
  
  print(ans)
  print(len(set(ans)))

Submission status: Wrong Answer

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")
MOD = 998244353


# 処理内容
def main():
    N, Q = map(int, input().split())
    c = list(map(int, input().split()))

    L = [0]*(N+1)
    d = [False]*(N+1)
    for i in range(N):
        if d[c[i]] == False:
            d[c[i]] = True
            L[i+1] += L[i] + 1
        else:
            L[i+1] = L[i]
    R = [0]*(N+1)
    d = [False]*(N+1)
    for i in range(N):
        if d[c[N-1-i]] == False:
            d[c[N-1-i]] = True
            R[i+1] += R[i] + 1
        else:
            R[i+1] = R[i]

    for _ in range(Q):
        l, r = map(int, input().split())
        print(max(L[r] - L[l-1], R[N-l+1] - R[N-r], 1))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n,q=map(int,input().split())
col=list(map(int,input().split()))
dd=defaultdict(lambda:[])
un={}
j=0
for i in col:
	dd[i].append(j)
	j=1
	
		


for _ in range(q):
	l,r=map(int,input().split())
	if l==r:
		print(1)
	else:
		l-=1
		r-=1
		c=0
		for i in dd:
			if dd[i][-1]>=l:
				if dd[i][0]<=r:
					c+=1	
		print(c)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n):
    res = [None] * n
    for i in range(n):
        res[i] = II()
    return res
def LIR(n):
    res = [None] * n
    for i in range(n):
        res[i] = LI_() + [i]
    return res
def FR(n):
    res = [None] * n
    for i in range(n):
        res[i] = IF()
    return res
mod = 1000000007
inf = float('INF')
#solve
def solve():
    n, q = LI()
    c = LI()
    lr = LIR(q)
    ans = [None] * q
    lr.sort(key=lambda x: x[1])
    dp = [-1] * (max(c) + 1)
    bit = [0] * (n + 1)
    def add(i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= n:
            bit[x - 1] += w
            x += x & -x
        return
    def sum(i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += bit[x - 1]
            x -= x & -x
        return res
    t = 0
    def f(t):
        l, r, j = lr[t]
        xr = sum(r)
        xl = sum(l-1)
        tmp = xr - xl
        ans[j] = tmp
    for i in range(n):
        ci = c[i]
        l = dp[ci]
        add(i, 1)
        dp[ci] = i
        if l != -1:
            add(l, -1)
        if t == q:
            break
    for ai in ans:
        print(ai) 
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

n, q = map(int, input().split())
c = [int(x) for x in input().split()]
from collections import Counter
left = []
right = []
for i in range(n + 1):
    temp = c[:i]
    left.append(len(Counter(temp)))
c = c[::-1]
for i in range(n + 1):
    temp = c[:i]
    right.append(len(Counter(temp)))

for _ in range(q):
    l, r = map(int, input().split())
    print(left[r] - left[l - 1] + right[n - l] - right[n - r - 1])

Submission status: Wrong Answer

Solution code:
N,Q=(int(x) for x in input().split())
c= list(map(int, input().split()))
tt=[0]
for i in range(Q):
    x1,x2=(int(x) for x in input().split())
    c1=c[(x1-1):(x2-1)]
    t=0
    for z in range(N):
        if c1.count((z+1))>0:
            t+=1
    tt2=[t]
    tt+=tt2
del tt[0]
for  r in tt:
    print(r)

Submission status: Wrong Answer

Solution code:
N, Q=map(int, input().split())
c=list(map(int, input().split()))
L=len(c)
c=[0]+c+[0]

s=[0]*(N+2)
t=[0]*(N+2)
colorcount=[0]*(N+1)

colors=[0]*(N+1)
for i in range(1, L+1):
  if colors[c[i]]==0:
    s[i]=s[i-1]+1
  else:
    s[i]=s[i-1]+0
  colors[c[i]]+=1
  
  colorcount[c[i]]=1
  
colors=[0]*(N+1)
for i in range(L, 0, -1):
  if colors[c[i]]==0:
    t[i]=t[i+1]+1
  else:
    t[i]=t[i+1]+0
  colors[c[i]]+=1
  
coln=sum(colorcount)
for _ in range(Q):
  l, r=map(int, input().split())
  if l==r:
    print(1)
    continue
  if r-l==1:
    if c[r]==c[l]:
      print(1)
    else:
      print(2)
    continue
  print(t[l]+s[r]-coln)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline

n,Q = map(int,input().split())
c = list(map(int,input().split()))


#####segfunc######
def segfunc(x,y):
    return x|y

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

for i in range(n):
    update(i,1<<c[i])

for i in range(Q):
    l,r = map(int,input().split())
    l -= 1

    res = query(l,r)
    print(res)

    print(popcnt(res))

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
C = list(map(int, input().split()))
tmp = set()
c_left = [0] * (N+1)
for i, c in enumerate(C):
    flg = 0 if c in tmp else 1
    c_left[i+1] = c_left[i] + flg
    tmp.add(c)

tmp = set()
c_right = [0] * (N+1)
for i, c in enumerate(reversed(C)):
    flg = 0 if c in tmp else 1
    c_right[i+1] = c_right[i] + flg
    tmp.add(c)
c_right.reverse()

for i in range(Q):
    l, r = map(int, input().split())
    if l == r:
        print(1)
    else:
        print(max(c_left[r] - c_left[l-1], c_right[l-1] - c_right[r]))

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
c=list(map(int,input().split()))

lst=[[] for _ in range(n+1)]
ruiseki=[0]*(n+1)
for i in range(1,n+1):
    ruiseki[i]+=ruiseki[i-1]
    if len(lst[c[i-1]])==0:
        ruiseki[i]+=1
        lst[c[i-1]].append(i)
    else:
        lst[c[i-1]].append(i)

print(ruiseki)
for i in range(q):
    l, r = map(int,input().split())
    if l==r:
        print(1)
    else:
        print(ruiseki[r]-ruiseki[l-1])

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
from math import ceil as C, floor as F, sqrt
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
 
ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())
 
n, q = I()
balls = Is()
 
for _ in range(q):
  l, r = I()
  print(len(CNT(balls[l:r+1])))

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    import collections
    N, Q = map(int, input().split())
    c = list(map(int, input().split()))
    lr = [tuple(map(int, input().split())) for i in range(Q)]

    s = set()
    C = [0]*N
    for i, x in enumerate(c):
        s.add(x)
        C[i] = len(s)
    print(C)

    for l, r in lr:
        l -= 1
        r -= 1
        if l == 0:
            print(C[r])
        else:
            print(len(collections.Counter(c[l:r+1]).keys()))


main()

Submission status: Wrong Answer

Solution code:
n,q=list(map(int,input().split()))
c=list(map(int,input().split()))
cd=[0 for i in range(n)]
d=[]
ds=0
cdd=[0 for i in range(n)]
dd=[]
dds=0
for i in range(n):
  if cd[c[i]-1]==0:
    cd[c[i]-1]=1
    ds+=1
  d.append(ds)
  if cdd[c[n-1-i]-1]==0:
    cdd[c[n-1-i]-1]=1
    dds+=1
  dd.append(dds)
    
dd.reverse()
s=ds
for i in range(q):
  qu=list(map(int,input().split()))
  print(d[qu[1]-1]+dd[qu[0]-1]-s)

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
c = list(map(int, input().split()))
cSetLen = len(set(c))

if cSetLen == 1:
    for i in range(q):
        print(1)
else:
    lr = []
    for i in range(q):
        l, r = map(int, input().split())
        temp = r + (r - l) // 2
        answer = 0
        while temp < r and answer < cSetLen:
            temp += 1
            answer = len(set(c[l - 1 : temp]))
        if answer == 0:
            print(1)
        else:
            print(answer)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
seg_unit = 0
 
 
def seg_f(x, y):
    return x | y
 
 
def build(seg, raw_data):
    N = len(seg) // 2
    seg[N:] = raw_data
    for i in range(N - 1, 0, -1):
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])
 
 
def set_val(seg, i, x):
    N = len(seg) // 2
    i += N
    seg[i] = x
    while i > 1:
        i >>= 1
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])
 
 
def fold(seg, l, r):
    vl = vr = 0
    N = len(seg) // 2
    l, r = l + N, r + N
    while l < r:
        if l & 1:
            vl = seg_f(vl, seg[l])
            l += 1
        if r & 1:
            r -= 1
            vr = seg_f(seg[r], vr)
        l, r = l >> 1, r >> 1
    return seg_f(vl, vr)
 
def main(N, S, query):
    seg = np.zeros(N + N, np.int64)
    build(seg, 1 << S)
    for q in query:
        a, b = q.split()
        a, b = int(a) - 1, int(b)
        x = fold(seg, a, b)
        print(bin(x).count('1'))
 
if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i8 = numba.int64
    cc = CC('my_module')
 
    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)
 
    seg_f = cc_export(seg_f, (i8, i8))
    build = cc_export(build, (i8[:], i8[:]))
    set_val = cc_export(set_val, (i8[:], i8, i8))
    fold = cc_export(fold, (i8[:], i8, i8))
    cc.compile()
 
from my_module import seg_f, build, set_val, fold
 
N, Q = map(int,readline().split())
S = np.array(list(map(int,readline().split())), np.int64) - 1

query = readlines()
 
main(N, S, query)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
from math import ceil as C, floor as F, sqrt
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
 
ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())
 
n, q = I()
balls = Is()
 
for _ in range(q):
  l, r = I()
  print(len(CNT(balls[l:r])))

Submission status: Wrong Answer

Solution code:

def query(ind,start,end,q1,q2,s):
    if q1>end or q2<start:
        return 0
    if q1<=start and q2>=end:
        for i in segment[ind][0]:
            s.add(i)
        return 0
    mid=(start+end)//2
    (query(2*ind+1,start,mid,q1,q2,s)+query(2*ind+2,mid+1,end,q1,q2,s))
    return len(s)
 
 
def build(ind,start,end):
    if start==end:
        segment[ind]=[[l[start]],1]
        return
    mid=(start+end)//2
    build(2*ind+1,start,mid)
    build(2*ind+2,mid+1,end)
    a=set()
    for i in (segment[2*ind+1][0]):
        a.add(i)
    for i in (segment[2*ind+2][0]):
        a.add(i)
    
    segment[ind]=[list(a),len(a)]
    
n,m=map(int,input().split())
l=list(map(int,input().split()))
segment=[0]*(4*n)
build(0,0,n-1)

for _ in range(m):
    a,b=map(int,input().split())
    print(query(0,0,n-1,a-1,b-1,set()))

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
c = list(map(int, input().split()))
cSetLen = len(set(c))

lr = []
for i in range(q):
    l, r = map(int, input().split())
    temp = r + (r - l) // 2
    answer = 0
    while temp < r and answer < cSetLen:
        temp += 1
        answer = len(set(c[l - 1 : temp]))
    if answer == 0:
        print(1)
    else:
        print(answer)

Submission status: Wrong Answer

Solution code:
def examA():
    X = I()
    if X<30:
        ans = "No"
    else:
        ans = "Yes"
    print(ans)
    return

def examB():
    N, D = LI()
    cnt = 0
    for _ in range(N):
        x, y = LI()
        if x**2+y**2<=D**2:
            cnt += 1
    ans = cnt
    print(ans)
    return

def examC():
    N = 10**7
    K = I()
    cur = 0
    now = 1
    ans = -1
    for i in range(N):
        cur += 7 * now
        cur %= K
        if cur==0:
            ans = i+1
            break
        now *= 10
        now %= K
    print(ans)
    return

def examD():
    N = I()
    C = SI()
    cnt = 0
    l = 0; r = N-1
    while(l<r):
        while(l<N):
            if C[l]=="W":
                break
            l += 1
        while(0<=r):
            if C[r]=="R":
                break
            r -= 1
        if l<r:
            cnt += 1
            l += 1
            r -= 1
    ans = cnt
    print(ans)
    return

def examE():
    N, K = LI()
    A = LI()
    if K==0:
        print(max(A))
        return
    l = 0; r = inf
    for _ in range(80):
        now = dec((l+r)/2)
        cnt = 0
        for a in A:
            cur = a//now
            cnt += cur
        if K<cnt:
            l = now
        else:
            r = now
        #print(now,cnt)
        #input()
    ans = l
    if ans - ans//1>0:
        ans += 1
    ans //=1
    #print(now)
    print(ans)
    return

def examF():
    # 0は絶対に入れない!!
    class Bit():
        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)
            return

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i & -i
            return s

        def add(self, i, x=1):
            # i==0 はだめ => 全部+1するとか
            while i <= self.size:
                self.tree[i] += x
                i += i & -i
            return

        def search(self, x):
            # 二分探索。和がx以上となる最小のインデックス(>= 1)を返す
            # maspyさんの参考　よくわかってない
            i = 0
            s = 0
            step = 1 << ((self.size).bit_length() - 1)
            while step:
                if i + step <= self.size and s + self.tree[i + step] < x:
                    i += step
                    s += self.tree[i]
                step >>= 1
            return i + 1

        def debug(self, k):
            return [self.sum(i) for i in range(k)]

        def inversion(self, A=[3, 10, 1, 8, 5]):
            res = 0
            for i, p in enumerate(A):
                self.add(p, 1)
                res += i + 1 - self.sum(p)
            return res
    N, Q = LI()
    C = LI()
    LR = []
    lastAppeared = [-1]*N
    for i in range(Q):
        l, r = LI()
        LR.append((l,r,i))
    LR.sort(key=lambda x:x[1])
    #print(LR)
    bit = Bit(N+1)
    ans = [0]*Q
    r = 0
    now = 0
    while(r<N):
        if now==Q:
            break
        l0, r0, i0 = LR[now]
        while(r<r0):
            c = C[r]-1
            if lastAppeared[c]>0:
                bit.add(lastAppeared[c],-1)
            lastAppeared[c] = r+1
            bit.add(lastAppeared[c]+1)
            r += 1
        #print(bit.debug(r))

        while(now<Q):
            l0,r0,i0 = LR[now]
            if r<r0:
                break
            #print(r,now)
            ans[i0] = bit.sum(r0+1)
            if l0>1:
                ans[i0] -= bit.sum(l0)
            now += 1


    for v in ans:
        print(v)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep,alphabet_convert
mod = 10**9 + 7
mod2 = 998244353
inf = dec("20000000000")
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 9

sys.setrecursionlimit(10**5)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import math
n,k = map(int,input().split())
log_list = list(map(float,input().split()))
log_list.sort()
 
cut_count = 0
while cut_count < k:
    max_index = log_list[n-1]
    next_index = log_list[n-2]
    div_count = 2
    while(log_list[n-1] / div_count >= log_list[n-2]):
        div_count+=1
    log_list[n-1] = log_list[n-1] / div_count
    cut_count += div_count - 1
    log_list.sort()
 
print(math.ceil((max(log_list))))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[16]:


N,K = map(int, input().split())
A = list(map(int, input().split()))


# In[42]:


cnt = 0
low = 0
high = max(A)
ans = max(A)
while low < high:
    mid = (high+low)/2
    cnt = sum([(x-0.001)//mid for x in A])
    if cnt <= K:
        high = mid
        ans = min(ans, int(-(-mid//1)))
    else:
        low = mid
    if high-low < 1/10**5:
        break
print(ans)


# In[ ]:

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
seg_unit = 0
 
 
def seg_f(x, y):
    return x | y
 
 
def build(seg, raw_data):
    N = len(seg) // 2
    seg[N:] = raw_data
    for i in range(N - 1, 0, -1):
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])
 
 
def set_val(seg, i, x):
    N = len(seg) // 2
    i += N
    seg[i] = x
    while i > 1:
        i >>= 1
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])
 
 
def fold(seg, l, r):
    vl = vr = 0
    N = len(seg) // 2
    l, r = l + N, r + N
    while l < r:
        if l & 1:
            vl = seg_f(vl, seg[l])
            l += 1
        if r & 1:
            r -= 1
            vr = seg_f(seg[r], vr)
        l, r = l >> 1, r >> 1
    return seg_f(vl, vr)
 
def main(N, S, query):
    seg = np.zeros(N + N, np.int64)
    build(seg, 1 << S)
    for q in query:
        a, b = q.split()
        a, b = int(a) - 1, int(b)
        x = fold(seg, a, b)
        print(bin(x).count('1'))
 
if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i8 = numba.int64
    cc = CC('my_module')
 
    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)
 
    seg_f = cc_export(seg_f, (i8, i8))
    build = cc_export(build, (i8[:], i8[:]))
    set_val = cc_export(set_val, (i8[:], i8, i8))
    fold = cc_export(fold, (i8[:], i8, i8))
    cc.compile()
 
from my_module import seg_f, build, set_val, fold
 
N, Q = map(int,readline().split())
S = np.array(list(map(int,readline().split())), np.int64)

query = readlines()
 
main(N, S, query)

Submission status: Wrong Answer

Solution code:
def find_index(arr, i):
    s = 0
    e = len(arr) - 1
    ans = 0
    while s <= e:
        mid = s + (e - s)//2
        if arr[mid] > i:
            ans = mid
            e = mid - 1
        else:
            s = mid + 1
    return ans
n, q = (int(i) for i in input().split())
nums = [int(i) for i in input().split()]
nums_info = []
repeated_idx = []
unique = set()
for i, num in enumerate(nums):
    if num in unique:
        repeated_idx.append(i)
        nums_info.append(len(unique))
        continue
    unique.add(num)
    nums_info.append(len(unique))
#print(nums_info)
for _ in range(q):
    s, e = (int(i) for i in input().split())
    s -= 2
    e -= 1
    if s < 0:
        print(nums_info[e])
        continue
    if (e - s) == nums_info[e] - nums_info[s]:
        print(e - s)
        continue
    count = nums_info[e] - nums_info[s]
    #print(count)
    idx = find_index(repeated_idx, s)
    new_search = set()
    #print(idx)
    for i in range(idx, min(len(repeated_idx),idx + e + 1)):
        if repeated_idx[i] > e:
            break
        new_search.add(nums[repeated_idx[i]])
    count += len(new_search)
    print(count)

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
a=[int(v) for v in input().split()]
an=[]
for j in range(q):
    l,r=map(int,input().split())
    q=len(set(a[l-1:r]))
    an.append(q)
for j in range(q):
    print(an[j])

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
seg_unit = 0
 
 
def seg_f(x, y):
    return x | y
 
 
def build(seg, raw_data):
    N = len(seg) // 2
    seg[N:] = raw_data
    for i in range(N - 1, 0, -1):
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])
 
 
def set_val(seg, i, x):
    N = len(seg) // 2
    i += N
    seg[i] = x
    while i > 1:
        i >>= 1
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])
 
 
def fold(seg, l, r):
    vl = vr = 0
    N = len(seg) // 2
    l, r = l + N, r + N
    while l < r:
        if l & 1:
            vl = seg_f(vl, seg[l])
            l += 1
        if r & 1:
            r -= 1
            vr = seg_f(seg[r], vr)
        l, r = l >> 1, r >> 1
    return seg_f(vl, vr)
 
def main(N, S, query):
    seg = np.zeros(N + N, np.int64)
    build(seg, 1 << S)
    for q in query:
        a, b = q.split()
        a, b = int(a) - 1, int(b)
        x = fold(seg, a, b)
        print(bin(x).count('1'))
 
if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i8 = numba.int64
    cc = CC('my_module')
 
    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)
 
    seg_f = cc_export(seg_f, (i8, i8))
    build = cc_export(build, (i8[:], i8[:]))
    set_val = cc_export(set_val, (i8[:], i8, i8))
    fold = cc_export(fold, (i8[:], i8, i8))
    cc.compile()
 
from my_module import seg_f, build, set_val, fold
 
N, Q = map(int,readline().split())
S = np.array(list(map(int,readline().split())), np.int64)
query = readlines()[:]
 
main(N, S, query)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
seg_unit = 0
 
 
def seg_f(x, y):
    return x | y
 
 
def build(seg, raw_data):
    N = len(seg) // 2
    seg[N:] = raw_data
    for i in range(N - 1, 0, -1):
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])
 
 
def set_val(seg, i, x):
    N = len(seg) // 2
    i += N
    seg[i] = x
    while i > 1:
        i >>= 1
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])
 
 
def fold(seg, l, r):
    vl = vr = 0
    N = len(seg) // 2
    l, r = l + N, r + N
    while l < r:
        if l & 1:
            vl = seg_f(vl, seg[l])
            l += 1
        if r & 1:
            r -= 1
            vr = seg_f(seg[r], vr)
        l, r = l >> 1, r >> 1
    return seg_f(vl, vr)
 
def main(N, S, query):
    seg = np.zeros(N + N, np.int64)
    build(seg, 1 << S)
    for q in query:
        a, b = q.split()
        a, b = int(a) - 1, int(b)
        x = fold(seg, a, b)
        print(bin(x).count('1'))
 
if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i8 = numba.int64
    cc = CC('my_module')
 
    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)
 
    seg_f = cc_export(seg_f, (i8, i8))
    build = cc_export(build, (i8[:], i8[:]))
    set_val = cc_export(set_val, (i8[:], i8, i8))
    fold = cc_export(fold, (i8[:], i8, i8))
    cc.compile()
 
from my_module import seg_f, build, set_val, fold
 
N, Q = map(int,readline().split())
S = np.array(list(map(int,readline().split())), np.int64)
query = readlines()[1:]
 
main(N, S, query)