質問リンク

カラーボール

問題の説明

各プレイヤーがボールの色と大きさを持っている場合、プレイヤーは自分のボールとは異なる色&大きさのボールを食べることができます.食べても自分の球の大きさや色は変わりません.このとき,各プレイヤーが食べられる全球の大きさの和を求める.
IN

球の個数(1≦N≦200000).

N行i次球の色の大きさ(1≦Ci≦N,1≦Si≦2000)

OUT

N個のi番目のバレーボールを持つプレイヤーがつかむことができるすべてのボールの大きさの合計は

である.

問題を解く

試してみる。

最初は探りに行ったが、結局ボールはせいぜい2万個で、タイムアウトした.
だから積算値を利用して求めたいです.
色番号

でソート

等のインデックスボールの積算値を求める.

サイズで

をソート

現在、ボールより小さいボールの簡単な累積値を求めている.

4から2を減算した値を出力します.

import sys

input = sys.stdin.readline
N = int(input())
balls = []
answer = [0]*N
same_colors = [0]*N

#[공번호, 색깔번호, 크기]
for i in range(N):
    balls.append([i] + list(map(int, input().split())))

#같은 색의 누적 값 구하기
balls.sort(key = lambda x: [x[1],x[2]])
for i in range(1,N):
    if balls[i][1] == balls[i-1][1]:
        same_colors[balls[i][0]] = same_colors[balls[i-1][0]] + balls[i-1][2]

#단순 누적 값 구하기
balls.sort(key = lambda x: x[2])
for i in range(1, N):
    answer[balls[i][0]] = answer[balls[i-1][0]] + balls[i-1][2]

for i in range(N):
    print(answer[i] - same_colors[i])

なぜなら.同じ大きさのボールに対する処理2.他の色の大きさのボールを処理していないので、

試してみる。

import sys

input = sys.stdin.readline
N = int(input())
balls = []
answer = [0]*N
same_colors = [0]*N

#[공번호, 색깔번호, 크기]
for i in range(N):
    balls.append([i] + list(map(int, input().split())))

#같은 색의 누적 값 구하기
balls.sort(key = lambda x: [x[1],x[2]])
count = 1
for i in range(1,N):
    if balls[i][1] == balls[i-1][1]:
        #같은 색 같은 크기의 공에 대해서
        if balls[i][2] == balls[i-1][2]:
            same_colors[balls[i][0]] = same_colors[balls[i-1][0]]
            count += 1
        else:
            same_colors[balls[i][0]] = same_colors[balls[i-1][0]] + balls[i-1][2]*count
            count = 1
    else:
        count = 1

#단순 누적 값 구하기 -> 크기가 같은 다른색 공
balls.sort(key = lambda x: x[2])
for i in range(1, N):
    #같은 크기의 공에 대해서
    if balls[i][2] == balls[i-1][2]:
        answer[balls[i][0]] = answer[balls[i-1][0]]
        count += 1
    else:
        answer[balls[i][0]] = answer[balls[i-1][0]] + balls[i-1][2] * count
        count = 1

for i in range(N):
    print(answer[i] - same_colors[i])

同じ大きさの公開数はcountで増えていますが、あまりよくありません.

たくらむ。

球のサイズ標準昇順配列

角功.
->私より小さいボールの重さを積算と対内色の積算で

加算

このボールの正解は積算-内色積算

である.

N = int(input())

sum_weight = 0
balls = [] 
color = [0] * (N+1)
ans = [0] * N

for i in range(N):
    balls.append([i] + list(map(int, input().split())))
# 크기 기준 오름차순 정렬
balls = sorted(balls,key=lambda l:l[2])

j = 0
for i in range(N):
    while balls[i][2] > balls[j][2]:
        sum_weight += balls[j][2]
        color[balls[j][1]] += balls[j][2]
        j += 1
	# 해당 공의 정답은 누적합에서 현재 자신의 색깔 누적합 값을 빼면 된다
    ans[balls[i][0]] = (sum_weight - color[balls[i][1]])

for x in ans:
    print(x)