Submission #1269357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269357		PagodePaiva	Examination (JOI19_examination)	Pypy 3	100 / 100	778 ms	199680 KiB

examination

import sys
def main():
    data = sys.stdin.readline().split()
    if not data:
        return
    N = int(data[0]); Q = int(data[1])
    S = [0]*N
    T = [0]*N
    for i in range(N):
        si, ti = sys.stdin.readline().split()
        S[i] = int(si); T[i] = int(ti)
    X = [0]*Q; Y = [0]*Q; Z = [0]*Q
    for j in range(Q):
        xj, yj, zj = sys.stdin.readline().split()
        X[j] = int(xj); Y[j] = int(yj); Z[j] = int(zj)
    P = [S[i] + T[i] for i in range(N)]
    # compress P and Z
    p_vals = set(P)
    for v in Z:
        p_vals.add(v)
    p_list = sorted(p_vals)
    p_map = {v:i+1 for i,v in enumerate(p_list)}
    # compress T and Y
    t_vals = set(T)
    for v in Y:
        t_vals.add(v)
    t_list = sorted(t_vals)
    t_map = {v:i+1 for i,v in enumerate(t_list)}
    # sort candidates by S descending and build list
    cand = list(range(N))
    cand.sort(key=lambda i: S[i], reverse=True)
    cand_list = [(S[i], t_map[T[i]], p_map[P[i]]) for i in cand]
    # build query lists
    list_PQ = []
    list_TQ = []
    for j in range(Q):
        Xj = X[j]; Yj = Y[j]; Zj = Z[j]
        K = Zj - Yj
        x2 = K + 1
        if x2 <= Xj:
            # sum redundant
            list_TQ.append((Xj, t_map[Yj], j, 1))
        else:
            # need full formula
            dz = p_map[Zj]
            list_PQ.append((Xj, dz, j, 1))
            list_PQ.append((x2, dz, j, -1))
            list_TQ.append((x2, t_map[Yj], j, 1))
    # process P-dimension queries (C1 - C2)
    ansP = [0]*Q
    list_PQ.sort(key=lambda x: x[0], reverse=True)
    bitP_size = len(p_list)
    bitP = [0] * (bitP_size + 1)
    total = 0
    pos = 0
    Ncand = N
    for S0, dz, j, mul in list_PQ:
        while pos < Ncand and cand_list[pos][0] >= S0:
            _, _, p_idx = cand_list[pos]
            i = p_idx
            while i <= bitP_size:
                bitP[i] += 1
                i += i & -i
            total += 1
            pos += 1
        # count P < Zj
        i = dz - 1
        s = 0
        while i > 0:
            s += bitP[i]
            i -= i & -i
        ansP[j] += mul * (total - s)
    # process T-dimension queries (rectangle or C3)
    ansT = [0]*Q
    list_TQ.sort(key=lambda x: x[0], reverse=True)
    bitT_size = len(t_list)
    bitT = [0] * (bitT_size + 1)
    total = 0
    pos = 0
    for S0, dy, j, mul in list_TQ:
        while pos < Ncand and cand_list[pos][0] >= S0:
            _, t_idx, _ = cand_list[pos]
            i = t_idx
            while i <= bitT_size:
                bitT[i] += 1
                i += i & -i
            total += 1
            pos += 1
        i = dy - 1
        s = 0
        while i > 0:
            s += bitT[i]
            i -= i & -i
        ansT[j] += mul * (total - s)
    # output final answers
    out = sys.stdout.write
    for j in range(Q):
        out(str(ansP[j] + ansT[j]) + "\n")

if __name__ == "__main__":
    main()

Compilation message (stdout)

Compiling 'examination.py'...

=======
  adding: __main__.pyc (deflated 51%)

=======

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57