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

Solution code:
from sys import stdin
a, max_per = map(int, input().split())
max_val = 0
book = [0]*(a+1)
for _ in stdin.read().splitlines() :
    a, v = map(int, _.split())
    book[a] += v
    if v < 0 :
        max_val = max(book)
        max_per = book.index(max_val)
    elif max_val < book[a] : max_per, max_val = a, book[a]
    elif max_val == book[a] and a < max_per : max_per = a
    print(max_per, max_val)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
n, max_per = map(int, input().split())
max_val = 0
book = [0]*(n+1)
for _ in stdin.read().splitlines() :
    a, v = map(int, _.split())
    book[a] += v
    if v < 0 :
        for _2 in range(max_val) :
            if (max_val - _2) in book :
                max_val -= _2
                break
        max_per = book.index(max_val)
    elif book[a] < max_val : pass
    elif max_val < book[a] : max_per, max_val = a, book[a]
    elif a < max_per : max_per = a
    print(max_per, max_val)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
n, max_per = map(int, input().split())
max_val = 0
book = [0]*(n+1)
for _ in stdin.read().splitlines() :
    a, v = map(int, _.split())
    book[a] += v
    if v < 0 :
        for _2 in [None]*max_val :
            if max_val in book : break
            max_val -= 1
        max_per = book.index(max_val)
    elif book[a] < max_val : pass
    elif max_val < book[a] : max_per, max_val = a, book[a]
    elif a < max_per : max_per = a
    print(max_per, max_val)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
n, max_per = map(int, input().split())
max_val = 0
book = [0]*(n+1)
for _ in stdin.read().splitlines() :
    a, v = map(int, _.split())
    book[a] += v
    if v < 0 :
        for _2 in [None]*max_val :
            if max_val in book : break
            max_val -= 1
        max_per = book.index(max_val)
    elif max_val < book[a] : max_per, max_val = a, book[a]
    elif max_val == book[a] and a < max_per : max_per = a
    print(max_per, max_val)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
n, max_per = map(int, input().split())
max_val = 0
book = [0]*(n+1)
for _ in stdin.read().splitlines() :
    a, v = map(int, _.split())
    book[a] += v
    if v < 0 :
        max_val = max(book)
        max_per = book.index(max_val)
    elif max_val < book[a] : max_per, max_val = a, book[a]
    elif max_val == book[a] and a < max_per : max_per = a
    print(max_per, max_val)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
n, q = [int(_) for _ in input().split()]
book = [0]*(n+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, v = [int(_2) for _2 in _.split()]
    book[a] += v
    if v < 0 :
        for _2 in [None]*max_val :
            if max_val in book : break
            max_val -= 1
        max_per = book.index(max_val)
    elif max_per == a : max_val += v
    elif max_val < book[a] : max_per, max_val = a, book[a]
    elif book[a] == max_val and a < max_per : max_per = a
    print(max_per, max_val)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
n, q = map(int, input().split())
book = [0]*(n+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, v = map(int, _.split())
    book[a] = book[a] + v
    if v < 0 :
        for _2 in [None]*max_val :
            if max_val in book : break
            max_val = max_val - 1
        max_per = book.index(max_val)
    elif max_per == a : max_val = book[a]
    elif max_val < book[a] : max_per, max_val = a, book[a]
    elif book[a] == max_val and a < max_per : max_per = a
    print(max_per, max_val)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
n, q = map(int, input().split())
book = [0]*(n+1)

max_per, max_val = map(int, input().split())
book[max_per] += max_val
print(max_per, max_val)

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
n, q = map(int, input().split())
book = [0]*(n+1)

max_per, max_val = map(int, input().split())
book[max_per] += max_val
print(max_per, max_val)

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

Submission status: Time Limit Exceeded

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



def main(args):
    #data = [(1, 4), (2, 5), (1, 3), (3, 6), (2, 7)]
    #data = [(1, 4), (2, 5), (2, -3),(3, 4), (1, -1)]
    fisher, event = [int(x) for x in input().split(' ')]
    fishes = [0 for _ in range(fisher + 1)]

    for _ in range(event):
        id, fish = [int(x) for x in input().strip().split(' ')]
        fishes[id] += fish
        max_fish = max(fishes)
        winner = fishes.index(max_fish)
        print('{} {}'.format(winner, max_fish))


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=0099
"""
import sys
import bisect



def main(args):
    #data = [(1, 4), (2, 5), (1, 3), (3, 6), (2, 7)]
    #data = [(1, 4), (2, 5), (2, -3),(3, 4), (1, -1)]
    fisher, event = [int(x) for x in input().split(' ')]
    fishes = [0 for _ in range(fisher + 1)]

    winner = 9999999999
    max_fish = -1
    for _ in range(event):
        id, fish = [int(x) for x in input().strip().split(' ')]
        fishes[id] += fish
        if fish > 0:
            if fishes[id] > max_fish:
                max_fish = fishes[id]
                winner = id
            elif fishes[id] == max_fish:
                winner = min(winner, id)
            else:
                pass
        else:
            max_fish = max(fishes)
            winner = fishes.index(max_fish)
        print('{} {}'.format(winner, max_fish))


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

Submission status: Time Limit Exceeded

Solution code:
[n,q] = map(int,input().split())

t = [ 0 for _ in range(n) ]
for _ in range(q):
    [a,v] = map(int,input().split())
    t[a-1] += v

    p = t.index(max(t))

    print("{} {}".format(p+1,t[p]))

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
s=[0]*-~n
for _ in[0]*q:
 a,v=map(int,input().split())
 s[a]+=v
 m=max(s)
 print(s.index(m),m)

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,raw_input().split())
L=[0]*n
for i in range(q):
    a,v=map(int,raw_input().split())
    L[a-1]+=v
    m=max(L)
    print L.index(m)+1,m

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,raw_input().split())
x={}
cmpare=lambda a,b:b[1]-a[1] if b[1]!=a[1] else a[0]-b[0]
for i in range(q):
    a,v=map(int,raw_input().split())
    x.setdefault(a,0)
    x[a]+=v
    print " ".join(map(str, sorted(x.items(),cmp=cmpare)[0]))

Submission status: Time Limit Exceeded

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


def main(readline=stdin.readline):
    n, q = (int(s) for s in readline().split())
    count = Counter()
    count[1] = 0
    for i in range(q):
        a, v = (int(s) for s in readline().split())
        count[a] += v
        it = iter(count.most_common())
        index, value = next(it)
        for i, v in it:
            if value != v:
                break
            if index > i:
                index = i
        print(index, value)
    exit()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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 = [[0, 0] 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
        source = max(base[a:a+100], key=keyfunc)
        dest = midway[a//100]
        dest[0] = source[0]
        dest[1] = source[1]
        print(*max(midway, key=keyfunc))
    exit()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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)

    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)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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//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], b+1):
            if value < v:
                value = v
                index = i
        midway[b//1000] = (index, value)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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//10000 + 1)

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

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

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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 = [(-maxsize, 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], b+1):
            if value < v:
                value = v
                index = i
        midway[b//1000] = (value, -index)

        value, index = max(midway)
        print(-index, value)
    exit()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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())
    #assert 1 <= n <= 1000000
    #assert 1 <= q <= 100000

    base = [0] * n

    for _ in range(q):
        a, v = (int(s) for s in readline().split())
        #assert 1 <= a <= n
        #assert -100 <= v <= 100

        base[a-1] += v

        index = 1
        value = base[0]
        for i, v in enumerate(base, 1):
            if value < v:
                value = v
                index = i

        print(index, value)
    exit()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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//1000 + 1)

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

        a -= 1
        base[a] += v

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

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

        print(index+1, value)
    exit()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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//1000 + 1)

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

        a -= 1
        base[a] += v

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

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

        print(index+1, value)
    exit()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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//1000 + 1)

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

        a -= 1
        base[a] += v

        b = a - a % 1000
        index = b
        value = base[b]
        end = b + 1000 if b + 1000 < n else n
        for i in xrange(b, end):
            if value < base[i]:
                value = base[i]
                index = i
        midway[b//1000] = index

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

        print(index+1, value)
    exit()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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]-1] += r[1]
	mx = max(s)
	print s.index(mx)+1, mx

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, raw_input().split())
s = [0]*n
for i in range(q):
	a,v = map(int, raw_input().split())
	s[a-1] += v
	ss = sorted(s,reverse=True)
	print s.index(ss[0])+1,ss[0]

Submission status: Accepted

Solution code:
def f(): return map(int,raw_input().split())
n,q=f()
a0,v0=0,0
A=[0]*(n+1)
for _ in range(q):
  a,v=f()
  A[a]+=v
  if a==a0 and A[a]<v0:
    v0=max(A)
    a0=A.index(v0)
  elif A[a]>v0: a0,v0=a,A[a]
  elif A[a]==v0 and a<a0: a0=a
  print a0,v0

Submission status: Accepted

Solution code:
def f(): return map(int,raw_input().split())
n,q=f()
a0,v0=0,0
A=[0]*(n+1)
for _ in range(q):
  a,v=f()
  A[a]+=v
  c=A[a]
  if a==a0 and c<v0:
    v0=max(A)
    a0=A.index(v0)
  elif c>v0: a0,v0=a,c
  elif c==v0 and a<a0: a0=a
  print a0,v0

Submission status: Accepted

Solution code:
def f(): return map(int,raw_input().split())
n,q=f()
a0,v0=0,0
A=[0]*(n+1)
for _ in range(q):
  a,v=f()
  A[a]+=v
  if a==a0 and A[a]<v0:
    v0=max(A)
    a0=A.index(v0)
  elif A[a]>v0:
    v0=A[a]
    a0=a
  elif A[a]==v0 and a<a0: a0=a
  print a0,v0

Submission status: Accepted

Solution code:
def f(): return map(int,raw_input().split())
n,q=f()
a0,v0=0,0
A=[0]*(n+1)
for _ in range(q):
  a,v=f()
  A[a]+=v
  if a==a0 and v<0:
    v0=max(A)
    a0=A.index(v0)
  elif A[a]>v0: a0,v0=a,A[a]
  elif A[a]==v0 and a<a0: a0=a
  print a0,v0

Submission status: Accepted

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: Accepted

Solution code:
inputs = lambda: map(int, raw_input().split())
n_, q = inputs()
n = 1
while n<=n_: n *= 2
data = [(0, -n)] * (2*n+1)
for t in xrange(q):
    a, v = inputs()
    i = a + (n-1)
    data[i] = (data[i][0]+v, -a)
    while i:
        i = (i - 1) / 2
        data[i] = max(data[2*i+1], data[2*i+2])
    p, q = data[0]
    print -q, p

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
inputs = lambda: map(int, raw_input().split())
n, q = inputs()
n += 1
que = [(0, 1, -1)]
data = [0] * n
T = [-1] * n
for t in xrange(q):
    a, v = inputs()
    data[a] += v
    T[a] = t

    heappush(que, (-data[a], a, t))
    while 1:
        v, k, p = heappop(que)
        if T[k] == p:
            print k, -v
            heappush(que, (v, k, p))
            break

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
inputs = lambda: map(int, raw_input().split())
n, q = inputs()
n += 1
que = [(0, 1, -1)]
data = [0] * n
T = [-1] * n
for t in xrange(q):
    a, v = inputs()
    data[a] += v
    T[a] = t

    heappush(que, (-data[a], a, t))
    v, k, p = que[0]
    while T[k]!=p:
        heappop(que)
        v, k, p = que[0]
    print k, -v

Submission status: Accepted

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


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:
        mx[0], mx[1] = spam()

    elif mx[1] < cnt[a]:
        mx[0], mx[1] = a, cnt[a]

    elif mx[1] == cnt[a] and mx[0] > a:
        mx[0], mx[1] = a, cnt[a]

    print("%d %d" % (mx[0], mx[1]))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
class Segtree():
    INT_MIN=-10**9
    ZERO=0

    def __init__(self,n):
        self.max_index=0
        self.n=1
        while self.n<n:
            self.n=self.n*2
        self.ary=[[self.ZERO,i] for i in xrange(2*self.n-1)]

    def max_update(self,k,a):
        k+=self.n-1
        self.ary[k][0]+=a
        while k>0:
            k=(k-1)/2
            self.ary[k][0]=max(self.ary[k*2+1][0],self.ary[k*2+2][0])
            if self.ary[k*2+1][0]>self.ary[k*2+2][0]:
                self.ary[k][1]=self.ary[k*2+1][1]
            elif self.ary[k*2+1][0]<self.ary[k*2+2][0]:
                self.ary[k][1]=self.ary[k*2+2][1]
            else:
                self.ary[k][1]=min(self.ary[k*2+1][1],self.ary[k*2+2][1])


n,q=map(int,raw_input().split())
par=Segtree(n)
for i in xrange(q):
    a,v=map(int,raw_input().split())
    a-=1
    par.max_update(a,v)
    print par.ary[0][1]-(par.n-1)+1,par.ary[0][0]

Submission status: Accepted

Solution code:
n,q=list(map(int, input().split()))
c=[0 for _ in range(n + 1)]
b=[0,0]
for _ in range(q):
    a,v=map(int, input().split())
    c[a]+=v
    if b[0]==a and v>0:b[1]+=v
    elif b[0]==a:mx=max(c[0:]);b[0],b[1]=min([i for i, value in enumerate(c) if value == mx]),mx
    elif b[1]<c[a]:b[0],b[1]=a,c[a]
    elif b[1]==c[a] and b[0] > a:b[0],b[1]=a,c[a]
    print(*b)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
import os


n, q = map(int, input().split())
scores = [0] * n

max_value = 0
max_index = 0
for i in range(q):
    a, v = map(int, input().split())

    # zero index
    a -= 1
    scores[a] += v

    # need speed than naive implementation

    if max_index == a and v < 0:
        max_value = max(scores)
        max_index = scores.index(max_value)

    elif max_value < scores[a]:
        max_index = a
        max_value = scores[a]

    elif max_value == scores[a] and a < max_index:
        max_index = a

    print(max_index + 1, max_value)

Submission status: Accepted

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 and a == winner:
        maxv = max(n)
        winner = n.index(maxv)
    elif n[a] > maxv:
            maxv, winner = n[a], a
    elif n[a] == maxv:
            winner = min(winner, a)
    print(winner, maxv)

Submission status: Accepted

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



def main(args):
    #data = [(1, 4), (2, 5), (1, 3), (3, 6), (2, 7)]
    #data = [(1, 4), (2, 5), (2, -3),(3, 4), (1, -1)]
    fisher, event = [int(x) for x in input().split(' ')]
    fishes = [0 for _ in range(fisher + 1)]

    winner = 9999999999
    max_fish = -1
    for _ in range(event):
        id, fish = [int(x) for x in input().strip().split(' ')]
        fishes[id] += fish
        if fish > 0:
            if fishes[id] > max_fish:
                max_fish = fishes[id]
                winner = id
            elif fishes[id] == max_fish:
                winner = min(winner, id)
            else:
                pass
        else:
            if winner == id:
                max_fish = max(fishes)
                winner = fishes.index(max_fish)
        print('{} {}'.format(winner, max_fish))


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

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())
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]>m:w,m=a,s[a]
 elif s[a]==m:w=min(w,a)
 print(w,m)

Submission status: Accepted

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]>m:w,m=a,s[a]
 elif s[a]==m and a<w:w=a
 print(w,m)

Submission status: Accepted

Solution code:
import queue
n,q=map(int,input().split())
p=queue.PriorityQueue()
s=[0]*-~n
for _ in[0]*q:
 a,v=map(int,input().split())
 s[a]+=v;p.put((-s[a],a))
 while 1:
  t=p.get()
  if -t[0]==s[t[1]]:print(t[1],-t[0]);p.put(t);break

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
def f():
 w=m=0;n,q=map(int,input().split());s=[0]*-~n
 for e in sys.stdin:
  a,v=map(int,e.split());s[a]+=v
  if v<0 and a==w:m=max(s);w=s.index(m)
  elif s[a]>m:w,m=a,s[a]
  elif s[a]==m:w=min(w,a)
  print(w,m)
if'__main__'==__name__:f()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
"""
セグメント木
"""

INF = 10 ** 20
n, q = map(int, input().split())

size = 1
while size < n:
  size *= 2
size = size * 2 - 1

seg_tree = [(INF, 0) for _ in range(size)]

def update(a, v):
  ind = (size - 1) // 2 + a
  prea, prev = seg_tree[ind]
  seg_tree[ind] = (a + 1, prev + v)
  while ind > 0:
    ind = (ind - 1) // 2
    ca1, cv1 = seg_tree[ind * 2 + 1]
    ca2, cv2 = seg_tree[ind * 2 + 2]
    if cv1 >= cv2:
      seg_tree[ind] = (ca1, cv1)
    else:
      seg_tree[ind] = (ca2, cv2)
      

for i in range(q):
  a, v = map(int, input().split())
  a -= 1
  update(a, v)
  print(seg_tree[0][0], seg_tree[0][1])

Submission status: Accepted

Solution code:
"""
セグメント木
"""

INF = 10 ** 20

def main():
  n, q = map(int, input().split())
  
  size = 1
  while size < n:
    size *= 2
  size = size * 2 - 1
  
  seg_tree = [(INF, 0) for _ in range(size)]
  
  def update(a, v):
    ind = (size - 1) // 2 + a
    prea, prev = seg_tree[ind]
    seg_tree[ind] = (a + 1, prev + v)

    while ind > 0:
      ind = (ind - 1) // 2
      ca1, cv1 = seg_tree[ind * 2 + 1]
      ca2, cv2 = seg_tree[ind * 2 + 2]
      if cv1 >= cv2:
        seg_tree[ind] = (ca1, cv1)
      else:
        seg_tree[ind] = (ca2, cv2)
        
  
  for i in range(q):
    a, v = map(int, input().split())
    update(a - 1, v)
    print(seg_tree[0][0], seg_tree[0][1])

main()

Submission status: Accepted

Solution code:
"""
セグメント木
"""

INF = 10 ** 20

def main():
  n, q = map(int, input().split())
  
  size = 1
  while size < n:
    size *= 2
  size = size * 2 - 1
  
  seg_tree = [(INF, 0) for _ in range(size)]
  
  def update(a, v):
    ind = (size - 1) // 2 + a
    prea, prev = seg_tree[ind]
    seg_tree[ind] = (a + 1, prev + v)

    while ind > 0:
      ind = (ind - 1) // 2
      ca1, cv1 = seg_tree[ind * 2 + 1]
      ca2, cv2 = seg_tree[ind * 2 + 2]
      if cv1 >= cv2:
        if seg_tree[ind] == (ca1, cv1): break
        seg_tree[ind] = (ca1, cv1)

      else:
        if seg_tree[ind] == (ca2, cv2): break
        seg_tree[ind] = (ca2, cv2)
        
  
  for i in range(q):
    a, v = map(int, input().split())
    update(a - 1, v)
    print(seg_tree[0][0], seg_tree[0][1])

main()

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