oj.uz

Submission #986815

# Submission time Handle Problem Language Result Execution time Memory
986815 2024-05-21T09:24:26 Z shikgom2 Poklon (COCI17_poklon) PyPy 3
0 / 140
 5000 ms 121356 KB 
import sys
input = sys.stdin.readline
from math import sqrt

mem = 100007

class Query:
    def __init__(self, l, r, k):
        self.l = l
        self.r = r
        self.k = k

    def __lt__(self, other):
        if self.l // sq == other.l // sq:
            return self.r > other.r
        return self.l // sq > other.l // sq

def add(g):
    global res, b
    if b[g] == 1:  # 이 수가 1번 등장했었다면
        res += 1
    elif b[g] == 2:  # 이 수가 2번 등장했었다면
        res -= 1
    b[g] += 1

def sub(g):
    global res, b
    if b[g] == 2:  # 이 수가 2번 등장했었다면
        res += 1
    elif b[g] == 3:  # 이 수가 3번 등장했었다면
        res -= 1
    b[g] -= 1

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

li = list(map(int, input().split()))
sq = int(sqrt(n))

y = []
for _ in range(m):
    q1, q2 = map(int, input().split())
    y.append(Query(q1 - 1, q2 - 1, len(y)))

y.sort(reverse=True)

b = [0] * (mem * 11)
res = 0
s, e = 0, 0
add(li[0])
ans = [0] * m

for q in y:
    ns, ne = q.l, q.r
    for i in range(s, ns):
        sub(li[i])
    for i in range(s - 1, ns - 1, -1):
        add(li[i])
    for i in range(e + 1, ne + 1):
        add(li[i])
    for i in range(e, ne, -1):
        sub(li[i])
    s, e = ns, ne
    ans[q.k] = res

print(*ans, sep='\n')

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 27104 KB Output isn't correct
2 Incorrect 68 ms 29364 KB Output isn't correct
3 Incorrect 89 ms 29740 KB Output isn't correct
4 Incorrect 117 ms 32560 KB Output isn't correct
5 Incorrect 666 ms 51648 KB Output isn't correct
6 Incorrect 665 ms 52852 KB Output isn't correct
7 Incorrect 1399 ms 77276 KB Output isn't correct
8 Incorrect 2679 ms 99652 KB Output isn't correct
9 Incorrect 3079 ms 121356 KB Output isn't correct
10 Execution timed out 5027 ms 112928 KB Time limit exceeded