読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

aoj 0099

contest contest-aoj language language-c++11

ワカサギ釣り | Aizu Online Judge
priority_queueは最大値を一番上に持ってくるSTLでこれを使えばとても便利.
データごとにpqに挿入し現在の魚の数を集計. 現在の状態と一致するものの中で最大のものを出力し残りはpopする.
こうすることによって古いデータの除去ができる.

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define DOWN(i,b,a) for(int i=b;i>=a;i--)

using namespace std;

typedef pair<int, int> Pii;

int main()
{
  int d[1000001] = {};
  int n,q; cin >> n >> q;
  priority_queue<Pii> pq;
  REP(i,q)
  {
    int a,v; cin >> a >> v;
    d[a] += v;
    pq.push(Pii(d[a],-a));
    while(!pq.empty())
    {
      Pii p = pq.top();
      if(p.first == d[-p.second])
      {
        cout << -p.second << " " << p.first << endl;
        break;
      }
      pq.pop();
    }
  }
  return 0;
}