Problem:


ワカサギ釣り大会 2

桧原湖でワカサギ釣り大会が行われました。今回はキャッチ＆リリースが推奨されているようです。

参加者番号と釣った匹数またはリリースした匹数を１つのイベントとして順番に読み込み、各イベントの直後に最も多くのワカサギを手元に獲得している参加者番号と匹数を出力するプログラムを作成してください。最も多く獲得している参加者が複数いる場合（あるいは全ての参加者が 0 匹の場合）は、その中で参加者番号が最も小さい一人を出力してください。

入力

入力は以下の形式で与えられる。

n q
a1 v1
a2 v2
: 
aq vq

n (1 ≤ n ≤ 1000000) は参加者の数、q (1 ≤ q ≤ 100000)はイベントの数を表す。ai (1 ≤ ai ≤ n)   vi ( -100 ≤ vi ≤ 100) は、i 番目のイベントで参加者 ai が vi 匹獲得あるいはリリースしたことを示す。vi は正の値が獲得、負の値がリリースを示し、0 が与えられることはない。

出力

各イベントごとに、最も多くのワカサギを手元に獲得している参加者の参加者番号と匹数を１つの空白区切りで１行に出力する。

入力例1

3 5
1 4 
2 5 
1 3
3 6
2 7

出力例1

1 4
2 5
1 7
1 7
2 12

入力例2

3 5
1 4 
2 5 
2 -3
3 4
1 -1

出力例2

1 4
2 5
1 4
1 4
3 4



Sample input:
3 5
1 4
2 5
1 3
3 6
2 7


Sample output:
1 4
2 5
1 7
1 7
2 12

Submission status: Accepted

Solution code:
# AOJ 0099 Surf Smelt Fishing Contest II
# Python3 2018.6.22 bal4u

import heapq
MAX = 1000000
SFT = 20	# 2**20 = 1048576 > MAX
Q = []

# tbl[0:キー, 1:Magic]
n, q = list(map(int, input().split()))
tbl = [0]*(n+1)
for i in range(q):
	id, v = list(map(int, input().split()))
	tbl[id] += v
	heapq.heappush(Q, ((-tbl[id] << SFT)|id, id, tbl[id]))
	while 1:
		f, id, v = Q[0]       # 要素の確認のみ
		if tbl[id] == v:
			print(id, v)
			break
		heapq.heappop(Q)

Submission status: Accepted

Solution code:
# AOJ 0099 Surf Smelt Fishing Contest II
# Python3 2018.6.22 bal4u

import heapq
SFT = 20	# 2**20 = 1048576 > MAX(1000000)
Q = []
n, q = list(map(int, input().split()))
tbl = [0]*(n+1)
for i in range(q):
	id, v = list(map(int, input().split()))
	tbl[id] += v
	f = tbl[id]
	heapq.heappush(Q, ((-f << SFT)|id, id, f))
	while 1:
		f, id, v = Q[0]       # 要素の確認のみ
		if tbl[id] == v:
			print(id, v)
			break
		heapq.heappop(Q)

Submission status: Accepted

Solution code:
import heapq
n,q = map(int,raw_input().split())
p = [0] * (n+1)
h = []
for u in xrange(q):
    a,v = map(int,raw_input().split())
    p[a] += v
    heapq.heappush(h,[-p[a],a])
    while True:
        top = heapq.heappop(h)
        if p[top[1]] == -top[0]:
            print "{} {}".format(top[1],-top[0])
            heapq.heappush(h,top)
            break

Submission status: Accepted

Solution code:
from collections import defaultdict
n,q=map(int,raw_input().split())
va=defaultdict(set)
av=defaultdict(int)
for i in range(q):
    a,v=map(int,raw_input().split())
    try:
        va[av[a]].remove(a)
        if va[av[a]]==set([]):
            del va[av[a]]
    except KeyError:
        pass
    av[a]+=v
    va[av[a]].add(a)
    m=max(va.keys())
    t=min(va[m])
    print t,m

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, exit


def main(readline=stdin.readline):
    n, q = (int(s) for s in readline().split())

    base = [0] * n
    midway = [0] * (n//100 + 1)
    last = [0] * (n//10000 + 1)

    for _ in range(q):
        a, v = (int(s) for s in readline().split())

        a -= 1
        base[a] += v

        b = a - a % 100

        index = b
        value = base[b]
        end = b + 100 if b + 100 < n else n
        for i in range(b, end):
            if value < base[i]:
                value = base[i]
                index = i
        midway[b//100] = index

        c = a - a % 10000
        cc = c // 100

        index = c
        value = base[c]
        for i in midway[cc:cc+100]:
            if value < base[i]:
                value = base[i]
                index = i
        last[c//10000] = index

        index = last[0]
        value = base[index]
        for i in last:
            if value < base[i]:
                value = base[i]
                index = i

        print(index+1, value)
    exit()


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, q = map(int, raw_input().split())
fish = [0] * n
ans1 = 0
ans2 = 0
for i in range(q):
	a, v = map(int, raw_input().split())
	fish[a-1] = fish[a-1] + v
	if ans1 == a and v < 0:
		ans1 = fish.index(max(fish)) + 1
		ans2 = max(fish)
	elif ans2 < fish[a-1]:
		ans1 = a
		ans2 = fish[a-1]
	elif ans2 == fish[a-1] and a < ans1:
		ans1 = a
	print "{} {}".format(ans1, ans2)

Submission status: Accepted

Solution code:
n, q = map(int, raw_input().split())
s = [0]*n
mx,mxa = 0, 0
for i in range(q):
	a,v = map(int, raw_input().split())
	s[a-1] += v
	if v > 0:
		if s[a-1] > mx:
			mx = s[a-1]
			mxa = a-1
		elif s[a-1] == mx:
			if a-1 < mxa:
				mxa = a-1
	elif v < 0:
		if a-1 == mxa:
			mx = max(s)
			mxa = s.index(mx)
	print mxa+1,mx

Submission status: Accepted

Solution code:
def solve():
    import heapq
    from sys import stdin
    lines = stdin
    
    n, q = map(int, lines.readline().split())
    
    # hq element: [number of caught fish, participant number]
    hq = [(0, i) for i in range(1, n + 1)]
    heapq.heapify(hq)
    fish = [0] * (n + 1) # number of caught fish
    
    ans = ""
    for i in range(q):
        a, v = map(int, lines.readline().split())
        # Because of Python heapq specification, negative values are used for fishing.
        v *= -1
        
        fish[a] += v
        heapq.heappush(hq, (fish[a], a))
        
        while hq[0][0] != fish[hq[0][1]]:
            heapq.heappop(hq)
        
        ans += f"{hq[0][1]} {-hq[0][0]}\n"
    
    print(ans, end="")

solve()

Submission status: Accepted

Solution code:
[n,q] = map(int,input().split())
 
t = [ 0 for _ in range(n) ]
 
max_idx = 0
max_val = 0
 
for _ in range(q):
    [a,v] = map(int,input().split())
    t[a-1] += v
 
    if max_idx == a-1:
        if v > 0:
            max_val = t[a-1]
        else:
            max_val = max(t)
            max_idx = t.index(max_val)
    elif t[a-1] > max_val:
        max_val = t[a-1]
        max_idx = a-1
    elif t[a-1] == max_val:
        if a-1 < max_idx:
            max_val = t[a-1]
            max_idx = a-1
 
    print("{} {}".format(max_idx+1,max_val))

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
result = [0 for i in range(n + 1)]
max_a = -1
max_v = 0

for i in range(q):
    a, v = map(int, input().split())
    result[a] += v
    if result[a] > max_v:
        max_a = a
        max_v = result[a]
    elif result[a] == max_v:
        if a < max_a:
            max_a = a
    elif a == max_a and result[a] <= max_v:
        max_a = result.index(max(result))
        max_v = result[max_a]
    print(max_a, max_v)

Submission status: Runtime Error

Solution code:
class SegmentTree:
    def __init__(self, n):
        n_ = 1
        while n_ < n: n_ *= 2
        self.n = n_
        self.data = [[0, -n_] for i in xrange(2*n_)]

    def add(self, k, a):
        idx = k + (self.n-1)
        data = self.data
        data[idx] = [data[idx][0] + a, -k]
        print data, idx, data[idx]
        while idx:
            idx = (idx - 1) / 2
            data[idx] = max(data[2*idx+1], data[2*idx+2])
            print idx, data[idx]

    def get(self):
        return self.data[0]

inputs = lambda: map(int, raw_input().split())
n, q = inputs()
st = SegmentTree(n)
for t in xrange(q):
    a, v = inputs()
    st.add(a, v)

    p, q = st.get()
    print -q, p

Submission status: Runtime Error

Solution code:
class SegmentTree:
    def __init__(self, n):
        n_ = 1
        while n_ < n: n_ *= 2
        self.n = n_
        self.data = [(0, -n_-1)] * (2*n_)

    def add(self, k, a):
        idx = k + (self.n-1)
        data = self.data
        data[idx] = (data[idx][0] + a, -k)
        while idx:
            idx = (idx - 1) / 2
            data[idx] = max(data[2*idx+1], data[2*idx+2])

    def get(self):
        return self.data[0]

inputs = lambda: map(int, raw_input().split())
n, q = inputs()
st = SegmentTree(n)
for t in xrange(q):
    a, v = inputs()
    st.add(a, v)

    p, q = st.get()
    print -q, p

Submission status: Runtime Error

Solution code:
n, q = list(map(int, input().split()))
cnt = [0 for _ in range(n + 1)]
cnt[0] = -1
mx = [0, -1]
for _ in range(q):
    a, v = list(map(int, input().split()))
    cnt[a] += v
    if mx[0] == a and v > 0:
        mx[1] += v
    elif mx[0] == a and v < 0:

        def spam():
            max_v = max(cnt)
            idx = min([i for i, value in enumerate(cnt) if value == max_v])
            return idx, max_v

        mx = spam()

    if cnt[a] > mx[1]:
        print("%d %d" % (a, cnt[a]))
        mx[0], mx[1] = a, cnt[a]
    else:
        print("%d %d" % (mx[0], mx[1]))

Submission status: Runtime Error

Solution code:
n, q = list(map(int, input().split()))
cnt = [0 for _ in range(n + 1)]
cnt[0] = -1
mx = [0, -1]


def spam():
    max_v = max(cnt)
    idx = min([i for i, value in enumerate(cnt) if value == max_v])
    return idx, max_v

for _ in range(q):
    a, v = list(map(int, input().split()))
    cnt[a] += v
    if mx[0] == a and v > 0:
        mx[1] += v
    elif mx[0] == a and v < 0:

        mx = spam()

    if cnt[a] > mx[1]:
        print("%d %d" % (a, cnt[a]))
        mx[0], mx[1] = a, cnt[a]
    else:
        print("%d %d" % (mx[0], mx[1]))

Submission status: Runtime Error

Solution code:
n, q = list(map(int, input().split()))
cnt = [0 for _ in range(n + 1)]
cnt[0] = -1
mx = [0, -1]


def spam():
#    max_v = max(cnt)
#    idx = min([i for i, value in enumerate(cnt) if value == max_v])
#    return idx, max_v
    return 1,1

for _ in range(q):
    a, v = list(map(int, input().split()))
    cnt[a] += v
    if mx[0] == a and v > 0:
        mx[1] += v
    elif mx[0] == a and v < 0:

        mx = spam()

    if cnt[a] > mx[1]:
        print("%d %d" % (a, cnt[a]))
        mx[0], mx[1] = a, cnt[a]
    else:
        print("%d %d" % (mx[0], mx[1]))

Submission status: Runtime Error

Solution code:
n, q = [int(el) for el in input().split(' ')]
data = [0] * n
ex_result = 0
for _ in range(q):
    a, v = [int(el) for el in input().split(' ')]
    data[a-1] += v
    if v < 0:
        result = ex_result
    else:
        result = max(data)
    print(data.index(result)+1, result)
    ex_result = result

Submission status: Runtime Error

Solution code:
n, q = [int(el) for el in input().split(' ')]
data = [0] * n
ex_result = 0
for _ in range(q):
    a, v = [int(el) for el in input().split(' ')]
    data[a-1] += v
    result = max(data)
    print(data.index(result)+1, result)
    ex_result = result

Submission status: Runtime Error

Solution code:
n, q = [int(el) for el in input().split(' ')]
data = [0] * n
ex_result, exx_result = 0,0
ex_index = 0
for _ in range(q):
    a, v = [int(el) for el in input().split(' ')]
    data[a-1] += v
    if ex_index != a:
        if v < 0: result = ex_result
        else: result = max(ex_result, data[a-1])
    elif ex_index == a:
        if v > 0: result = data[a-1]
        else: result = max(data[a-1], exx_result)
    index = data.index(result)+1
    print(index, result)
    exx_result = ex_result
    ex_result = result
    ex_index = index

Submission status: Runtime Error

Solution code:
n, q = [int(el) for el in input().split(' ')]
data = [0] * n
ex_result, exx_result = 0,0
ex_index = 0
for _ in range(q):
    a, v = [int(el) for el in input().split(' ')]
    data[a-1] += v
    if ex_index != a:
        if v < 0: result = ex_result
        else: result = max(ex_result, data[a-1])
    elif ex_index == a:
        if v > 0: result = data[a-1]
        else: result = max(exx_result, data[a-1])
    index = data.index(result)+1
    print(index, result)
    exx_result = ex_result
    ex_result = result
    ex_index = index

Submission status: Runtime Error

Solution code:
n, q = [int(el) for el in input().split(' ')]
data = [0] * n
ex_result,exx_result = 0,0
ex_index = 0
for _ in range(q):
    a, v = [int(el) for el in input().split(' ')]
    data[a-1] += v
    if ex_index != a:
        if v < 0: result = ex_result
        else: result = max(ex_result, data[a-1])
    elif ex_index == a:
        if v > 0: result = data[a-1]
        else: result = max(exx_result, data[a-1])
    index = data.index(result)+1
    print(index, result)
    exx_result = ex_result
    ex_result = result
    ex_index = index

Submission status: Runtime Error

Solution code:
n, q = [int(el) for el in input().split(' ')]
data = [0] * n
ex_result, exx_result = 0, 0
ex_index, exx_index  = 0, 0
for _ in range(q):
    a, v = [int(el) for el in input().split(' ')]
    data[a-1] += v
    if ex_index != a:
        if v < 0: result = ex_result
        else: result = max(ex_result, data[a-1])
    else:
        if v > 0: result = data[a-1]
        else:
            if exx_index == a: result = max(data)
            else: result = max(exx_result, data[a-1])
    index = data.index(result) + 1
    print(index, result)
    exx_result = ex_result
    ex_result = result
    exx_index = ex_index
    ex_index = index

Submission status: Runtime Error

Solution code:
#-*- coding: utf_8 -*-

a = [int(x) for x in input().split()]
n, q = a[0], a[1]
memo = [0] * n

for i in range(q):
    debug(memo)
    nq = [int(x) for x in input().split()]
    a, v = nq[0] - 1, nq[1]
    memo[a] += v
    mx = max(memo)
    print(str(memo.index(mx) + 1) + " " +  str(mx))

Submission status: Runtime Error

Solution code:
import bisect
from math import modf

[n,q]=map(int,raw_input().split())
decp=1./(n+2)
A=[0 for i in range(n+1)]
B=[1-decp*(i+1) for i in range(n)]

for i in range(q):
    [a,v]=map(int,raw_input().split())
    pp=A[a]+ (1-decp*(a+1))
    A[a]+=v
    remind=bisect.bisect_left(B,pp)
    B.pop(remind)
    bisect.insort(B,pp+v)
    decimal, integer = modf(B[-1])
    print int(round((1-decimal)*(n+2)-1,0)) , int(integer)

Submission status: Runtime Error

Solution code:
import bisect
from math import modf

[n,q]=map(int,raw_input().split())
decp=1./(n+2)
A=[0 for i in range(n+1)]
B=[1-decp*(i+1) for i in range(1,n+1)]
B.sort()
for i in range(q):
    [a,v]=map(int,raw_input().split())
    pp=A[a]+ (1-decp*(a+1))
    A[a]+=v
    remind=bisect.bisect_left(B,pp)
    B.pop(remind)
    bisect.insort(B,pp+v)
    decimal, integer = modf(B[-1])
    print int(round((1-decimal)*(n+2)-1,0)) , int(integer)

Submission status: Runtime Error

Solution code:
n, q = map(int, input().split())
n = [0]*(n+1)
maxv = winner = 0
for _ in range(q):
    a, v = map(int, input().split())
    n[a] += v
    if v < 0:
        maxv, winner = max(n), n.index(maxv)
    else:
        if n[a] > maxv:
            maxv, winner = n[a], a
        elif n[a] == maxv:
            winner = n.index(maxv)
    print(winner, maxv)

Submission status: Runtime Error

Solution code:
from collections import deque
n, q = [int(_) for _ in input().split()]
book = deque()
for _ in range(n+1) : book.append(0)
for _ in range(q) :
    a, v = [int(_2) for _2 in input().split()]
    book[a] += v
    print(book.index(max(book)), max(book))

Submission status: Runtime Error

Solution code:
from array import array
n, q = [int(_) for _ in input().split()]
book = array('b', [0] * (n+1))
for _ in range(q) :
    a, v = [int(_2) for _2 in input().split()]
    book[a] += v
    print(book.index(max(book)), max(book))

Submission status: Runtime Error

Solution code:
from array import array
n, q = [int(_) for _ in input().split()]
book = array('b', [0] * (n+1))
max_per, max_val = n, 0
for _ in range(q) :
    a, v = [int(_2) for _2 in input().split()]
    book[a] += v
    if 0 <= v :
        if max_val < book[a] : max_per, max_val = a, book[a]
        elif max_val == book[a] and a < max_per : max_per = a
    elif v < 0 :
        max_val = max(book)
        max_per = book.index(max_val)
    print(max_per, max_val)

Submission status: Runtime Error

Solution code:
from sys import stdin
n = [int(_) for _ in input().split()]
book = [0]*(n[0]+1)

max_per, max_val = [int(_) for _ in input().split()]
book[max_per] += max_val
print(max_per, max_val)

for _ in stdin.read().splitlines() :
    a = [int(_2) for _2 in _.split()]
    book[a[0]] += a[1]
    if a[1] < 0 :
        for _2 in [None]*book[a[0]] :
            if max_val in book : break
            max_val -= 1
        max_per = book.index(max_val)
    elif book[a[0]] < max_val : pass
    elif max_val < book[a[0]] : 
        max_val = book[a[0]]
        if max_per != a : max_per = a[0]
    elif a[0] < max_per : max_per = a[0]
    print(max_per, max_val)

Submission status: Runtime Error

Solution code:
from sys import stdin
n = [int(_) for _ in input().split()]
book = [0]*(n[0]+1)

max_per, max_val = [int(_) for _ in input().split()]
book[max_per] += max_val
print(max_per, max_val)

for _ in stdin.read().splitlines() :
    a = [int(_2) for _2 in _.split()]
    book[a[0]] += a[1]
    if a[1] < 0 :
        for _2 in [None]*book[a[0]] :
            if max_val in book : break
            max_val -= 1
        max_per = book.index(max_val)
    elif book[a[0]] < max_val : pass
    elif max_val < book[a[0]] : 
        max_val = book[a[0]]
        if max_per != a[0] : max_per = a[0]
    elif a[0] < max_per : max_per = a[0]
    print(max_per, max_val)

Submission status: Runtime Error

Solution code:
from sys import stdin
n = [int(_) for _ in input().split()]
book = [0]*(n[0]+1)

max_per, max_val = [int(_) for _ in input().split()]
book[max_per] += max_val
print(max_per, max_val)

for _ in stdin.read().splitlines() :
    a = [int(_2) for _2 in _.split()]
    book[a[0]] += a[1]
    if a[1] < 0 :
        for _2 in [None]*book[a[0]] :
            if max_val in book : break
            max_val -= 1
        max_per = book.index(max_val)
    elif max_per == a[0] : max_val += a[1]
    elif max_val < book[a[0]] : max_per, max_val = a[0], book[a[0]]
    elif book[a[0]] == max_val and a[0] < max_per : max_per = a[0]
    print(max_per, max_val)

Submission status: Runtime Error

Solution code:
n,q=map(int,input().split())
s=[0]*-~n
w=m=0
for _ in[0]*q:
 a,v=map(int,input().split())
 s[a]+=v
 if v<0 and a==w:m=max(s),w=s.index(m)
 elif s[a]>maxv:w,m=a,s[a]
 elif s[a]==maxv:w=min(w,a)
 print(w,m)

Submission status: Runtime Error

Solution code:
n,q=map(int,input().split())
s=[0]*-~n
w=m=0
for _ in[0]*q:
 a,v=map(int,input().split())
 s[a]+=v
 if v<0 and a==w:m=max(s);w=s.index(m)
 elif s[a]>maxv:w,m=a,s[a]
 elif s[a]==maxv:w=min(w,a)
 print(w,m)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, exit
from collections import Counter


def keyfunc(data):
    return (data[1], -data[0])


def main(readline=stdin.readline):
    n, q = (int(s) for s in readline().split())

    base = tuple([i+1, 0] for i in range(n))
    midway = [base[i*100] for i in range(n//100 + 1)]

    for i in range(q):
        a, v = (int(s) for s in readline().split())
        a -= 1
        base[a][1] += v
        a -= a % 100
        midway[a//100] = max(base[a:a+100], key=keyfunc)
        print(*max(midway, key=keyfunc))
    exit()


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, exit, maxsize


def main(readline=stdin.readline):
    n, q = (int(s) for s in readline().split())

    base = [0] * n
    midway = [(1, -maxsize)] * (n//100 + 1)
    last = [(1, -maxsize)] * (n//10000 + 1)

    for _ in range(q):
        a, v = (int(s) for s in readline().split())
        a -= 1
        base[a] += v

        b = a - a % 100
        index = value = -maxsize
        for i, v in enumerate(base[b:b+100], b+1):
            if value < v:
                value = v
                index = i
        midway[b//100] = (index, value)

        c = b - b % 100
        index = value = -maxsize
        for i, v in midway[c:c+100]:
            if value < v:
                value = v
                index = i
        last[c//100] = (index, value)

        index = value = -maxsize
        for i, v in last:
            if value < v:
                value = v
                index = i
        print(index, value)
    exit()


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, exit, maxsize


def main(readline=stdin.readline):
    n, q = (int(s) for s in readline().split())

    base = [0] * n
    midway = [0] * (n//1000 + 1)

    for _ in range(q):
        a, v = (int(s) for s in readline().split())
        a -= 1
        base[a] += v

        b = a - a % 1000

        index = value = -maxsize
        for i, v in enumerate(base[b:b+1000]):
            if value < v:
                index = i
                value = v
        midway[b] = index

        value = index = -maxsize
        for i in midway:
            if value < base[i]:
                value = base[i]
                index = i

        print(index+1, value)
    exit()


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n, q = map(int, raw_input().split())
s = [0 for i in range(n)]
a = [map(int, raw_input().split()) for i in range(q)]
for r in a:
	s[r[0]] += r[1]
	mx = max(s)
	print s.index(mx)+1, mx