Problem:


プログラミングコンテスト

白虎大学では毎年プログラミングコンテストが開催されています。チームの総数をNとしたとき、チームには1からNのチームIDがそれぞれ割り当てられています。コンテストは全てのチームの得点が0の状態から開始し、L秒間連続して行われます。

今年のコンテストは、テレビで中継されることになりました。コンテストの間テレビに映るのは、その時点で最も得点の高いチームだけです。ただし、該当するチームが複数いるときは、その中でチームIDの一番小さいチームが映ります。映すべきチームが変わると、瞬時にカメラが切り替わります。

あなたはコンテストのログを入手しました。ログには、あるチームの得点が変化した時のレコードがすべて含まれています。各レコードは「チームdがコンテスト開始t秒後の時点でx点獲得した」という形式で与えられています。なお、減点される場合もあるので、現在の得点が0より小さくなることもあります。

コンテストのログを入力とし、コンテスト開始から終了までの間にテレビに映った時間が最も長いチームのIDを報告するプログラムを作成してください。

入力

入力は1つのデータセットからなる。入力は以下の形式で与えられる。

N R L
d1 t1 x1
d2 t2 x2
:
dR tR xR

１行目は３つの整数からなる。N(2 ≤ N ≤ 100000)はチーム数、R(0 ≤ R ≤ 1000000)はログに含まれるレコードの数である。L(1 ≤ L ≤ 1000000)はコンテストの時間（長さ）を表す。続くR行に各レコードの情報が与えられる。各レコードはチームdi(1 ≤ di ≤ N)がコンテスト開始ti(0 < ti < L)秒後の時点でxi(-1000 ≤ xi ≤ 1000)点獲得あるいは減点されたことを示す。ただし、ti, xiは整数であり、ti-1 ≤ tiである。

出力

コンテスト開始から終了までの間にテレビに映った時間が最も長いチームのIDを１行に出力する。ただし、最も長いチームが複数あるときは、その中でチームIDの一番小さいチームを出力する。

入力例 1

3 4 600
3 100 5
1 200 10
2 400 20
3 500 20

出力例 1

1

入力例 2

3 5 600
3 100 5
1 200 10
2 300 30
1 400 -8
2 400 -27

出力例 2

3



Sample input:
3 4 600
3 100 5
1 200 10
2 400 20
3 500 20


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappush, heapify

def solve():
    file_input = sys.stdin
    N, R, L = map(int, file_input.readline().split())
    
    hq = []
    m = {}
    for i in range(1, N + 1):
        team = [0, i, 0]
        heappush(hq, team)
        m[i] = team
    
    time = 0
    for line in file_input:
        d, t, x = map(int, line.split())
        m[d][0] -= x
        hq[0][2] += t - time
        time = t
        heapify(hq)
    hq[0][2] += L - time
    ans_team = max(hq, key = lambda x: (x[2], -x[1]))
    print(ans_team[1])

solve()

Submission status: Time Limit Exceeded

Solution code:
n, r, l = map(int, input().split())
p = [0 for i in range(n + 1)] #得点
p[0] = -10e10
t = [0 for i in range(n + 1)] #時間
now = [1, 0]
for _ in range(r):
    re = list(map(int, input().split()))
    t[now[0]] += re[1] - now[1]
    p[re[0]] += re[2]
    now[1] = re[1]
    now[0] = p.index(max(p))
t[now[0]] += l - now[1]
print(t.index(max(t)))

Submission status: Time Limit Exceeded

Solution code:
n, r, l = map(int, input().split())
p, s = [0] * n, [0] * n
tn = 0
for _ in range(r):
    d, t, x = map(int, input().split())
    s[p.index(max(p))] += t - tn
    tn = t
    p[d - 1] += x
s[p.index(max(p))] += l - tn
print(s.index(max(s)) + 1)

Submission status: Time Limit Exceeded

Solution code:
n,r,l=map(int,raw_input().split())
id_t=[0]*n
id_x=[0]*n
log=[map(int,raw_input().split()) for i in range(r)]
log.insert(0,[1,0,0])
log.append([1,l,0])
for i in range(1,r+2):
	id_t[id_x.index(max(id_x))]+=log[i][1]-log[i-1][1]
	id_x[log[i][0]-1]+=log[i][2]
print id_t.index(max(id_t))+1

Submission status: Time Limit Exceeded

Solution code:
n,r,l=map(int,raw_input().split())
log=[map(int,raw_input().split()) for i in range(r)]
log.insert(0,[1,0,0])
log.append([1,l,0])
id_t=[0]*n
id_x=[0]*n
max_id=0
for i in range(1,r+2):
	cur_id=log[i][0]-1
	id_t[max_id]+=log[i][1]-log[i-1][1]
	id_x[cur_id]+=log[i][2]
	if log[i][2]<0:
		max_id=id_x.index(max(id_x))
	elif id_x[max_id]<id_x[cur_id] or (id_x[max_id]==id_x[cur_id] and max_id>cur_id):
		max_id=cur_id
print id_t.index(max(id_t))+1

Submission status: Accepted

Solution code:
import sys
f = sys.stdin

n, r, l = map(int, f.readline().split())

appearance = [0] * n
point = [0] * n

top = 0
pre_t = 0
for line in f:
    d, t, x = map(int, line.split())
    d -= 1 # 0-index?????????
    
    appearance[top] += t - pre_t
    pre_t = t
    
    point[d] += x
    if 0 < x and top != d:
        if point[top] < point[d]:
            top = d
        elif point[top] == point[d] and d < top:
            top = d
    elif x < 0 and top == d:
        top = point.index(max(point))

appearance[top] += l - pre_t

print(1 + appearance.index(max(appearance)))

Submission status: Accepted

Solution code:
n, r, l = map(int, raw_input().split())
time = [0]*n
score = [0]*n
top_id = 0
d = [map(int, raw_input().split()) for _ in range(r)] + [[1,l,0]]
cur_time = 0
for e in sorted(d, key = lambda x: x[1]):
    cur_id = e[0] - 1
    time[top_id] += e[1] - cur_time
    cur_time = e[1]
    score[cur_id] += e[2]
    if cur_id == top_id and e[2] < 0:
        top_id = score.index(max(score))
    elif score[top_id] < score[cur_id] or (score[top_id] == score[cur_id] and top_id > cur_id):
        top_id = cur_id
print time.index(max(time)) + 1

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0282

"""
import sys
from sys import stdin
from heapq import heappop, heappush
input = stdin.readline


pq = []                         # list of entries arranged in a heap
entry_finder = {}               # mapping of tasks to entries
REMOVED = float('inf')      # placeholder for a removed task

def add_team(score, team):
    if team in entry_finder:
        remove_team(team)
    entry = [-score, team]
    entry_finder[team] = entry
    heappush(pq, entry)

def remove_team(team):
    entry = entry_finder.pop(team)
    entry[-1] = REMOVED

def pop_team():
    while pq:
        score, team = heappop(pq)
        if team is not REMOVED:
            del entry_finder[team]
            return score, team
    raise KeyError('pop from an empty priority queue')


def main(args):
    N, R, L = map(int, input().split(' '))
    on_tv = [0] * (N + 1)       #  ????????????????????¬???????????£??????????????????????¨?
    scores = [0] * (N + 1)       #  ????????????????????¨?????????

    #for i in range(1, N+1):
    #    add_team(0, i)
    
    add_team(0, 1)

    last_time = 0
    need_pop = True
    top_score = 0

    for i in range(R):
        d, t, x = [int(x) for x in input().split(' ')]
        if need_pop:
            need_pop = False
            top_score, team = pop_team()
            if d != team:
                add_team(scores[team], team)

        on_tv[team] += (t - last_time)

        scores[d] += x
        add_team(scores[d], d)
        if x > 0 and scores[d] > top_score:
            need_pop = True

        last_time = t

    t = L
    score, team = pop_team()
    on_tv[team] += (t - last_time)

    print(on_tv.index(max(on_tv)))


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

def solve():
    file_input = sys.stdin
    N, R, L = map(int, file_input.readline().split())
    
    hq = []
    m = {}
    for i in range(1, N + 1):
        team = [0, i, 0]
        heappush(hq, team)
        m[i] = team
    
    time = 0
    for line in file_input:
        d, t, x = map(int, line.split())
        hq[0][2] += t - time
        time = t
        
        scored_team = m[d][:]
        scored_team[0] -= x
        heappush(hq, scored_team)
        m[d][2] = -1
        m[d] = scored_team
        
        while hq[0][2] == -1:
            heappop(hq)
    hq[0][2] += L - time
    ans_team = max(hq, key = lambda x: (x[2], -x[1]))
    print(ans_team[1])

solve()

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop, heapreplace

def solve():
    file_input = sys.stdin
    N, R, L = map(int, file_input.readline().split())
    
    pq = [[0, i, 0] for i in range(1, N + 1)]
    m = dict(zip(range(1, N + 1), pq))
    
    pre_t = 0
    for line in file_input:
        d, t, x = map(int, line.split())
        team = pq[0]
        team[2] += t - pre_t
        pre_t = t
        
        if team[1] == d:
            team[0] -= x
            if x < 0:
                heapreplace(pq, team)
        else:
            scored_team = m[d][:]
            scored_team[0] -= x
            heappush(pq, scored_team)
            m[d][2] = -1
            m[d] = scored_team
        
        while pq[0][2] == -1:
            heappop(pq)
    pq[0][2] += L - pre_t
    ans_team = max(pq, key = lambda x: (x[2], -x[1]))
    print(ans_team[1])

solve()

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop, heapreplace

def solve():
    file_input = sys.stdin
    N, R, L = map(int, file_input.readline().split())
    
    pq = [[0, i] for i in range(1, N + 1)]
    m = dict(zip(range(1, N + 1), pq))
    time = [0] * (N + 1)
    INVALID = -1
    
    pre_t = 0
    for line in file_input:
        d, t, x = map(int, line.split())
        top_team = pq[0]
        time[top_team[1]] += t - pre_t
        pre_t = t
        
        if top_team[1] == d:
            top_team[0] -= x
            if x < 0:
                heapreplace(pq, top_team)
        else:
            scored_team = m[d][:]
            scored_team[0] -= x
            heappush(pq, scored_team)
            m[d][1] = INVALID
            m[d] = scored_team
        
        while pq[0][1] == INVALID:
            heappop(pq)
    time[pq[0][1]] += L - pre_t
    print(time.index(max(time)))

solve()

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop, heapreplace
 
def solve():
    file_input = sys.stdin
    N, R, L = map(int, file_input.readline().split())
     
    pq = [[0, i] for i in range(1, N + 1)]
    m = dict(zip(range(1, N + 1), pq))
    time = [0] * (N + 1)
    INVALID = -1
     
    pre_t = 0
    for line in file_input:
        d, t, x = map(int, line.split())
        top_team = pq[0]
        time[top_team[1]] += t - pre_t
        pre_t = t
         
        if top_team[1] == d:
            top_team[0] -= x
            if x < 0:
                heapreplace(pq, top_team)
        else:
            scored_team = m[d][:]
            scored_team[0] -= x
            heappush(pq, scored_team)
            m[d][1] = INVALID
            m[d] = scored_team
         
        while pq[0][1] == INVALID:
            heappop(pq)
    time[pq[0][1]] += L - pre_t
    print(time.index(max(time)))
 
solve()

Submission status: Accepted

Solution code:
n,r,l=map(int,raw_input().split())
log=[map(int,raw_input().split()) for i in range(r)]
log.insert(0,[1,0,0])
log.append([1,l,0])
id_t=[0]*n
id_x=[0]*n
max_id=0
for i in range(1,r+2):
	cur_id=log[i][0]-1
	id_t[max_id]+=log[i][1]-log[i-1][1]
	id_x[cur_id]+=log[i][2]
	if cur_id==max_id and log[i][2]<0:
		max_id=id_x.index(max(id_x))
	elif id_x[max_id]<id_x[cur_id] or (id_x[max_id]==id_x[cur_id] and max_id>cur_id):
		max_id=cur_id
print id_t.index(max(id_t))+1

Submission status: Accepted

Solution code:
def findMaxId(id_x):
	max_x=0
	max_id=0
	for i in range(n):
		if id_x[i]>max_x:
			max_x=id_x[i]
			max_id=i
	return max_id
	
n,r,l=map(int,raw_input().split())
log=[map(int,raw_input().split()) for i in range(r)]
log.insert(0,[1,0,0])
log.append([1,l,0])
id_t=[0]*n
id_x=[0]*n
max_id=0
for i in range(1,r+2):
	cur_id=log[i][0]-1
	id_t[max_id]+=log[i][1]-log[i-1][1]
	id_x[cur_id]+=log[i][2]
	if cur_id==max_id and log[i][2]<0:
		max_id=findMaxId(id_x)
	elif id_x[max_id]<id_x[cur_id] or (id_x[max_id]==id_x[cur_id] and max_id>cur_id):
		max_id=cur_id
print id_t.index(max(id_t))+1

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from heapq import *

N, R, L = map(int, input().split())
score = [0]*N
pq = []

for i in range(N):
    heappush(pq, (-score[i], i))

prev_t = 0
now = 0
time = [0]*N

for _ in range(R):
    di, ti, xi = map(int, input().split())
    time[now] += ti-prev_t
    prev_t = ti
    heappush(pq, (-score[now], now))
    heappush(pq, (-score[di-1]-xi, di-1))
    score[di-1] += xi
    
    while True:
        s, idx = heappop(pq)
        s *= -1
        
        if score[idx]==s:
            break

    now = idx

time[now] += L-prev_t
max_t = 0
ans = -1

for i in range(N):
    if time[i]>max_t:
        max_t = time[i]
        ans = i+1

print(ans)

Submission status: Runtime Error

Solution code:
N, R, L = list(map(int, input().split(" ")))

i = 1
while i<N*2:
	i<<=1

t = [0 for j in range(N)]

time = [0 for j in range()]


def foo(a,x):
	newmax = -1
	def bar(k,a,x,l,r):
		mid = a<(l+r)//2
		if r-l == 1:
			t[k] += x
			newmax = r
			return(t[k])
		elif a<mid:
			t[k] = max(bar(k*2,a,x,l,mid), t[k])
		else:
			t[k] = max(bar(k*2+1,a,x,mid,r), t[k])

	bar(1,a,x,0,i//2)
	return(t[1],newmax)

nowtime = 0
nowmax = 0
nowpoint = 0

for i in range(R):
	d,t,x = map(int, input().split(" "))
	time[nowmax] += d-nowtime
	nowtime = d
	newpoint, newmax = foo(d,x)
	if nowpoint < newpoint:
		nowmax = newmax
		nowpoint = newpoint
	elif nowpoint == newpoint:
		nowmax = min(nowmax, newmax)

time[nowmax] += L-nowtime
print(time.index(max(time)))



N, R, L = list(map(int, input().split(" ")))

i = 1
while i<N*2:
	i<<=1

t = [0 for j in range(N)]

time = [0 for j in range()]


def foo(a,x):
	newmax = -1
	def bar(k,a,x,l,r):
		mid = a<(l+r)//2
		if r-l == 1:
			t[k] += x
			newmax = r
			return(t[k])
		elif a<mid:
			t[k] = max(bar(k*2,a,x,l,mid), t[k])
		else:
			t[k] = max(bar(k*2+1,a,x,mid,r), t[k])

	bar(1,a,x,0,i//2)
	return(t[1],newmax)

nowtime = 0
nowmax = 0
nowpoint = 0

for i in range(R):
	d,t,x = map(int, input().split(" "))
	time[nowmax] += d-nowtime
	nowtime = d
	newpoint, newmax = foo(d,x)
	if nowpoint < newpoint:
		nowmax = newmax
		nowpoint = newpoint
	elif nowpoint == newpoint:
		nowmax = min(nowmax, newmax)

time[nowmax] += L-nowtime
print(time.index(max(time)))

Submission status: Runtime Error

Solution code:
N, R, L = list(map(int, input().split(" ")))

i = 1
while i<N*2:
	i<<=1

tree = [0 for j in range(i)]

time = [0 for j in range(N)]


def foo(a,x):
	newmax = -1
	def bar(k,a,x,l,r):
		mid = (l+r)//2
		print(l,mid,r)
		if r-l == 1:
			tree[k] += x
			newmax = r
			return(tree[k])
		elif a<mid:
			tree[k] = max(bar(k*2,a,x,l,mid), tree[k])
		else:
			tree[k] = max(bar(k*2+1,a,x,mid,r), tree[k])

	bar(1,a,x,0,i//2)
	return(tree[1],newmax)

nowtime = 0
nowmax = 0
nowpoint = 0

for j in range(R):
	d,t,x = map(int, input().split(" "))
	time[nowmax] += d-nowtime
	nowtime = d
	newpoint, newmax = foo(d,x)
	if nowpoint < newpoint:
		nowmax = newmax
		nowpoint = newpoint
	elif nowpoint == newpoint:
		nowmax = min(nowmax, newmax)

time[nowmax] += L-nowtime
print(time.index(max(time)))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0282
TLE
"""
import sys
from sys import stdin
from heapq import heappop, heappush
input = stdin.readline


pq = []                         # list of entries arranged in a heap
entry_finder = {}               # mapping of tasks to entries
REMOVED = '<removed-task>'      # placeholder for a removed task

def add_team(team, score):
    if team in entry_finder:
        remove_team(team)
    entry = [score, team]
    entry_finder[team] = entry
    heappush(pq, entry)

def remove_team(team):
    entry = entry_finder.pop(team)
    entry[-1] = REMOVED

def pop_team():
    while pq:
        score, team = heappop(pq)
        if team is not REMOVED:
            del entry_finder[team]
            return team
    raise KeyError('pop from an empty priority queue')


def main(args):
    N, R, L = map(int, input().split())

    on_tv = [0] * (N + 1)       #  ????????????????????¬???????????£??????????????????????¨?
    scores = [0] * (N + 1)       #  ????????????????????¨?????????l

    add_team(1, 0)
    last_time = 0
    for i in range(R):
        d, t, x = [int(x) for x in input().split()]
        team = pop_team()
        on_tv[team] += (t - last_time)
        if d != team:
            add_team(team, scores[team])

        scores[d] -= x
        add_team(d, scores[d])
        last_time = t

    t = L
    team = pop_team()
    on_tv[team] += (t - last_time)

    print(on_tv.index(max(on_tv)))


if __name__ == '__main__':
    main(sys.argv[1:])