oj.uz

Submission #986813

# Submission time Handle Problem Language Result Execution time Memory
986813 2024-05-21T09:22:40 Z shikgom2 Poklon (COCI17_poklon) PyPy 3
0 / 140
 5000 ms 133216 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

for a in ans:
    print(a)
#print(*ans, sep='\n')

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 26932 KB Output isn't correct
2 Incorrect 78 ms 29356 KB Output isn't correct
3 Incorrect 92 ms 29584 KB Output isn't correct
4 Incorrect 126 ms 32908 KB Output isn't correct
5 Incorrect 661 ms 53152 KB Output isn't correct
6 Incorrect 660 ms 54248 KB Output isn't correct
7 Incorrect 1397 ms 78220 KB Output isn't correct
8 Incorrect 2697 ms 105452 KB Output isn't correct
9 Incorrect 3182 ms 133216 KB Output isn't correct
10 Execution timed out 5033 ms 121412 KB Time limit exceeded