AOJ 282 Programming Contest

方針としては、以下の2種類の操作がO( log(n) )程度で行えれば時間内に解けるだろと考えられる。

1. i番目のチームの得点をx増やす
2. 全チームの内, 得点が最大のチームの番号を求める

よってセグメント木でRange Minimum Queryを実装したら良さそうという発想に至る。
ただし、以下の様に少し工夫する必要がある。

1. (当たり前だが) 最小値(Minimum)ではなく最大値を求める
2. データとなる数列は, a[i] := pair(i番目のチームの得点, -i) とする

特に二つ目が重要で, これにより以下の効用が得られる。

1. 最大値を求める際に, 最大値をとるチームの番号を同時に求めることができる
2. pairには比較演算子が定義されているので, 問題で指示されている (チームの得点が高い順 => 得点が同じなら番号の若い順) での順序付けが楽に行える

セグメント木によるRMQの実装は蟻本のサンプルを拝借して改変。

#include <cstdio>
#include <algorithm>
#define INF 1000000000
#define MAX_N 1 << 18
using namespace std;

typedef pair<int, int> P;

int N, R, L;
int dur[MAX_N];
int n;
P score[2 * MAX_N - 1];

void init(int n_){
  n = 1;
  while(n < n_) n *= 2;
  for(int i = 0; i < 2 * n - 1; i++)
    score[i] = P(-INF, -INF);
}

void update(int k_, int a){
  int k = k_ + n - 1;
  score[k] = P(a, - k_);
  while(k > 0){
    k = (k - 1) / 2;
    score[k] = max(score[k * 2 + 1], score[k * 2 + 2]);
  }
}

P query(int a, int b, int k, int l, int r){
  if(r <= a || b <= l)
    return P(-INF, -INF);
  
  if(a <= l && r <= b)
    return score[k];
  
  else{
    P vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
    P vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
    return max(vl, vr);
  }
}

int top_id(){
  return - query(0, N, 0, 0, n).second;
}

int add_score(int id, int x){
  update(id, score[id + n - 1].first + x);
}

int main(){
  scanf("%d %d %d", &N, &R, &L);

  init(N);

  for(int i = 0; i < N; i++)
    update(i, 0);

  int time = 0;
  for(int i = 0; i < R; i++){
    int d, t, x;
    scanf("%d %d %d", &d, &t, &x);

    dur[top_id()] += t - time;
    time = t;
    add_score(d - 1, x);
  }
  dur[top_id()] += L - time;

  int ans, max_dur = -1;
  for(int i = 0; i < N; i++)
    if(max_dur < dur[i]){
      max_dur = dur[i];
      ans = i + 1;
    }

  printf("%d\n", ans);
}