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: Wrong Answer

Solution code:
import sys

N, R, L = [int(s) for s in input().split()]
views = [0] * (N + 1)
scores = [0] * (N + 1)
top = 1
T = 0

for s in sys.stdin:
    d, t, x = [int(s) for s in s.split()]
    views[top] += t - T
    scores[d] += x
    if d == top and x < 0:
        top = scores.index(max(scores))
    elif scores[d] > scores[top] or (scores[d] == scores[top] and d < top):
        top = d
    T = t

views[top] += L - T
team, _ = max(enumerate(views), key=lambda x: x[1])
print(team)

Submission status: Wrong Answer

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)]

tree[0] = -1

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

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

nowtime = 0
nowmax = 0
nowpoint = 0

for j in range(R):
	d,t,x = map(int, input().split(" "))
	d -= 1
	time[nowmax] += t-nowtime
	nowtime = t
	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))+1)

Submission status: Wrong Answer

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)]

tree[0] = -1

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

	bar(1,a,x,0,i//2)
	# print("tree[0]",tree[0])
	return(tree[1],tree[0])

nowtime = 0
nowmax = 0
nowpoint = 0

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

time[nowmax] += L-nowtime

# print(tree)
# print(time)

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

Submission status: Wrong Answer

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 = '<removed-task>'      # 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 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(i, 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(scores[team], team)

        scores[d] -= x
        add_team(scores[d], 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:])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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 i
	
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: Time Limit Exceeded

Solution code:
n, r, l = map(int, input().split())
leaf_num = 1
while leaf_num < n:
  leaf_num *= 2
tree = [None] * (leaf_num * 2 - 1)

for i in range(n):
  tree[leaf_num - 1 + i] = (i, 0)

def set_value(index):
  if leaf_num - 1 <= index <= leaf_num * 2 - 2:
    return tree[index]
  t1 = set_value(index * 2 + 1)
  t2 = set_value(index * 2 + 2)
  if t1 == None and t2 == None:
    return None
  else:
    tree[index] = (t1[0], t1[1])
    return tree[index]

def update(index):
  if index <= -1:return 
  elif leaf_num - 1 <= index <= leaf_num * 2 - 2:
    update((index - 1) // 2)
  else:
    left = tree[index * 2 + 1]
    right = tree[index * 2 + 2]
    if right == None:
      tree[index] = left
    else:
      if left[1] < right[1]:
        tree[index] = right
      else:
        tree[index] = left
    update((index - 1) // 2)

set_value(0)
score = [0] * n
last_time = 0
for _ in range(r):
  d, t, x = map(int, input().split())
  index, _ = tree[0]
  score[index] += t - last_time
  last_time = t
  d -= 1
  tree[leaf_num - 1 + d] = (tree[leaf_num - 1 + d][0], tree[leaf_num - 1 + d][1] + x)
  update(leaf_num - 1 + d)

score[tree[0][0]] += l - last_time
print(score.index(max(score)) + 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def main():
  n, r, l = map(int, input().split())
  leaf_num = 1
  while leaf_num < n:
    leaf_num *= 2
  INF = 10 ** 20
  tree = [None] * (leaf_num * 2 - 1)
  save = [0] * n
  
  for i in range(n):
    tree[leaf_num - 1 + i] = i
  
  def set_value(index):
    if leaf_num - 1 <= index <= leaf_num * 2 - 2:
      return tree[index]
    t1 = set_value(index * 2 + 1)
    t2 = set_value(index * 2 + 2)
    tree[index] = t1
    return tree[index]
  
  def update(index):
    index = (index - 1) // 2
    while index >= 0:
      left = tree[index * 2 + 1]
      right = tree[index * 2 + 2]
      if right == None:
        index = (index - 1) // 2
        continue
      tree[index] = right if save[right] > save[left] else left
      index = (index - 1) // 2

  
  set_value(0)
  score = [0] * n
  last_time = 0
  for _ in range(r):
    d, t, x = map(int, input().split())
    score[tree[0]] += t - last_time
    last_time = t
    save[d - 1] += x
    update(leaf_num + d - 2)
  
  score[tree[0]] += l - last_time
         
  print(score.index(max(score)) + 1)
main()

Submission status: Time Limit Exceeded

Solution code:
n, r, l = map(int, input().split())
point, time = [], []

for i in range(n):
    point.append(0)
    time.append(0)

now, tv = 0, 0
for i in range(r):
    d, t, x = map(int, input().split())
    time[tv] += t - now
    now = t
    point[d-1] += x
    m = sorted(point, reverse=True)[0]
    i = 0
    while True:
        if point[i] == m:
            tv = i
            break
        i += 1

time[tv] += l - now

m = sorted(time, reverse=True)[0]
i = 0
while True:
    if time[i] == m:
        print(i+1)
        break
    i += 1

Submission status: Time Limit Exceeded

Solution code:
n, r, l = map(int, input().split())
point, time = [], []
rev = {0: []}
for i in range(n):
    point.append(0)
    time.append(0)
    rev[0].append(i)

now, tv = 0, 0
for i in range(r):
    d, t, x = map(int, input().split())
    time[tv] += t - now
    now = t
    rev[point[d-1]].remove(d-1)
    point[d-1] += x
    if point[d-1] in rev:
        rev[point[d-1]].append(d-1)
    else:
        rev[point[d-1]] = [d-1]
    if tv != d-1: 
        if point[tv] == point[d-1]:
            tv = min(tv, d-1)
        elif point[tv] < point[d-1]:
            tv = d-1
    elif x < 0:
        tv = min(rev[max(point)])

time[tv] += l - now

m = max(time)
i = 0
while True:
    if time[i] == m:
        print(i+1)
        break
    i += 1

Submission status: Time Limit Exceeded

Solution code:
n, r, l = map(int, input().split())
point, time = [], []
rev = {0: []}
for i in range(n):
    point.append(0)
    time.append(0)
    rev[0].append(i)

now, tv, tmax = 0, 0, 0
for i in range(r):
    d, t, x = map(int, input().split())
    time[tv] += t - now
    now = t
    m = point[d-1]
    rev[point[d-1]].remove(d-1)
    point[d-1] += x
    if point[d-1] in rev:
        rev[point[d-1]].append(d-1)
    else:
        rev[point[d-1]] = [d-1]
    if tv != d-1: 
        if point[tv] == point[d-1]:
            tv = min(tv, d-1)
        elif point[tv] < point[d-1]:
            tv = d-1
    elif x < 0:
        if rev[m] != []:
            tv = min(rev[m])
        else:
            tv = min(rev[max(point)])

time[tv] += l - now

m = max(time)
i = 0
while True:
    if time[i] == m:
        print(i+1)
        break
    i += 1

Submission status: Time Limit Exceeded

Solution code:
class Node:

    def __init__(self, x, y):
        self.score = 0
        self.team = x
        self.x = x
        self.y = y
        self.l = self.r = None

        if y - x > 1:
            mid = (x + y) / 2
            self.l = Node(x, mid)
            self.r = Node(mid, y)

    def add(self, i, x):
        if self.x <= i < self.y:
            if self.l or self.r:
                self.l.add(i, x)
                self.r.add(i, x)
                if self.l.score >= self.r.score:
                    self.score = self.l.score
                    self.team = self.l.team
                if self.r.score > self.l.score:
                    self.score = self.r.score
                    self.team = self.r.team
            else:
                self.score += x

N, R, L = [int(s) for s in raw_input().split()]
n = Node(0, N)
views = [0] * N
T = 0

for _ in xrange(R):
    d, t, x = [int(s) for s in raw_input().split()]
    views[n.team] += t - T
    n.add(d-1, x)
    T = t

views[n.team] += L - T
team, _ = max(enumerate(views), key=lambda x: x[1])
print team + 1

Submission status: Time Limit Exceeded

Solution code:
import sys

class Node:

    def __init__(self, x, y):
        self.score = 0
        self.team = x
        self.x = x
        self.y = y
        self.l = self.r = None

        if y - x > 1:
            mid = (x + y) / 2
            self.l = Node(x, mid)
            self.r = Node(mid, y)

    def add(self, i, x):
        if self.x <= i < self.y:
            if self.l or self.r:
                self.l.add(i, x)
                self.r.add(i, x)
                if self.l.score >= self.r.score:
                    self.score = self.l.score
                    self.team = self.l.team
                if self.r.score > self.l.score:
                    self.score = self.r.score
                    self.team = self.r.team
            else:
                self.score += x

N, R, L = [int(s) for s in raw_input().split()]
n = Node(0, N)
views = [0] * N
T = 0

for s in sys.stdin:
    d, t, x = [int(s) for s in s.split()]
    views[n.team] += t - T
    n.add(d-1, x)
    T = t

views[n.team] += L - T
team, _ = max(enumerate(views), key=lambda x: x[1])
print team + 1

Submission status: Time Limit Exceeded

Solution code:
import sys

class SegmentTree:

    def __init__(self, N):
        self.N = N
        inner = 1
        while inner < N:
            inner *= 2
        self.inner = inner - 1
        self.nodes = [(0, 0)] * (inner * 2) # (score, team)

    def update(self, d, x):
        index = self.leaf(d)
        self.nodes[index] = (self.nodes[index][0] + x, d)
        while index > 0:
            p = (index - 1) / 2
            l = p * 2 + 1
            r = p * 2 + 2
            if self.nodes[l][0] >= self.nodes[r][0]:
                self.nodes[p] = self.nodes[l]
            if self.nodes[r][0] > self.nodes[l][0]:
                self.nodes[p] = self.nodes[r]
            index = p

    def leaf(self, d):
        return self.inner + d


N, R, L = [int(s) for s in raw_input().split()]
st = SegmentTree(N)
views = [0] * N
scores = [0] * N
T = 0

for s in sys.stdin:
    d, t, x = [int(s) for s in s.split()]
    views[st.nodes[0][1]] += t - T
    st.update(d - 1, x)
    T = t

views[st.nodes[0][1]] += L - T
team, _ = max(enumerate(views), key=lambda x: x[1])
print team + 1

Submission status: Time Limit Exceeded

Solution code:
import sys

class SegmentTree:

    def __init__(self, N):
        self.N = N
        inner = 1
        while inner < N:
            inner *= 2
        self.inner = inner - 1
        self.nodes = [(0, 0)] * (inner * 2) # (score, team)

    def update(self, d, x):
        index = self.leaf(d)
        self.nodes[index] = (self.nodes[index][0] + x, d)
        while index > 0:
            p = (index - 1) // 2
            l = p * 2 + 1
            r = p * 2 + 2
            if self.nodes[l][0] >= self.nodes[r][0]:
                self.nodes[p] = self.nodes[l]
            elif self.nodes[r][0] > self.nodes[l][0]:
                self.nodes[p] = self.nodes[r]
            index = p

    def leaf(self, d):
        return self.inner + d


N, R, L = [int(s) for s in input().split()]
st = SegmentTree(N)
views = [0] * N
scores = [0] * N
T = 0

for s in sys.stdin:
    d, t, x = [int(s) for s in s.split()]
    views[st.nodes[0][1]] += t - T
    st.update(d - 1, x)
    T = t

views[st.nodes[0][1]] += L - T
team, _ = max(enumerate(views), key=lambda x: x[1])
print(team + 1)

Submission status: Time Limit Exceeded

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 teams to entries
REMOVED = 10000000000 #'<removed-team>'      # placeholder for a removed team

def add_team(team, score=0):
    'Add a new team or update the score of an existing team'
    if team in entry_finder:
        remove_team(team)
    entry = [-score, team]
    entry_finder[team] = entry
    heappush(pq, entry)

def remove_team(team):
    'Mark an existing team as REMOVED.  Raise KeyError if not found.'
    entry = entry_finder.pop(team)
    entry[-1] = REMOVED

def pop_team():
    'Remove and return the lowest score team. Raise KeyError if empty.'
    while pq:
        e = heappop(pq)
        score, team = e
        if team is not REMOVED:
            del entry_finder[team]
            return team, -score
    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

    for i in range(1, N+1):
        add_team(i, 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)
        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:])

Submission status: Time Limit Exceeded

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 teams to entries
REMOVED = 10000000000 #'<removed-team>'      # placeholder for a removed team

def add_team(team, score=0):
    'Add a new team or update the score of an existing team'
    if team in entry_finder:
        remove_team(team)
    entry = [-score, team]
    entry_finder[team] = entry
    heappush(pq, entry)

def remove_team(team):
    'Mark an existing team as REMOVED.  Raise KeyError if not found.'
    entry = entry_finder.pop(team)
    entry[-1] = REMOVED

def pop_team():
    'Remove and return the lowest score team. Raise KeyError if empty.'
    while pq:
        e = heappop(pq)
        score, team = e
        if team is not REMOVED:
            del entry_finder[team]
            return team, -score
    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:])

Submission status: Time Limit Exceeded

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 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)

    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(scores[team], team)

        scores[d] -= x
        add_team(scores[d], 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:])

Submission status: Time Limit Exceeded

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 = 100000000      # 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 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)

    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(scores[team], team)

        scores[d] += x
        add_team(scores[d], 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:])

Submission status: Time Limit Exceeded

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 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)

    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(scores[team], team)

        scores[d] += x
        add_team(scores[d], 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:])

Submission status: Time Limit Exceeded

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 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)

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

        scores[d] += x
        add_team(scores[d], d)

        last_time = t
        last_score = x
        last_team = d

    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:])

Submission status: Time Limit Exceeded

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
from collections import defaultdict
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 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)       #  ????????????????????¨?????????
    scores = defaultdict(int)

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

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

        scores[d] += x
        add_team(scores[d], d)

        last_time = t
        last_score = x
        last_team = d

    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:])

Submission status: Time Limit Exceeded

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)

    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: Time Limit Exceeded

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

"""
import sys
from sys import stdin
input = stdin.readline


class RMQ(object):
    INT_MAX = 2**31 - 1

    def __init__(self, nn, init_val=0):
        self.n = 1
        while self.n < nn:
            self.n *= 2
        self.dat = [init_val] * ((2 * self.n)-1)

    def update(self, k, a):
        # A[k]???a?????´??°?????????????????°???????????¨?????´??°
        k += (self.n - 1)
        self.dat[k] = a

        while k > 0:
            k = (k - 1) // 2        #  ??????index??????
            self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2]) #  ???????????¨??????????????????????°?????????????????????´??°

    def query(self, a, b, k, l, r):
        # [a, b)???????°????????±??????? (0????????§b???????????????)
        # ??????????????¨?????????query(a, b, 0, 0, n)?????¢??§??????????????????k, l, r???????????????????????´??°?????????
        if r <= a or b <= l:        #  ?????????????????§??¨??????????????????
            return RMQ.INT_MAX
        if a <=l and r <= b:
            return self.dat[k]           #  ???????????°???????????????????????§????????°????????¨??????????????????????°?????????????????????????
        else:
            vl = self.query(a, b, k*2+1, l, (l+r)//2) #  ????????°????????????????°????
            vr = self.query(a, b, k*2+2, (l+r)//2, r) #  ????????°????????????????°????
            return min(vl, vr)

    def find(self, s, t):
        return self.query(s, t+1, 0, 0, self.n)



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

    rq = RMQ(N+1)

    last_time = 0
    for i in range(R):
        d, t, x = [int(x) for x in input().split(' ')]
        top_score = rq.find(1, N)
        top_team = scores.index(-top_score)
        on_tv[top_team] += (t - last_time)

        scores[d] += x
        rq.update(d, -scores[d])

        last_time = t

    t = L
    top_score = rq.find(1, N)
    top_team = scores.index(-top_score)
    on_tv[top_team] += (t - last_time)

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


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