[AOJ] No. 0282 プログラミングコンテスト

2020年12月17日

問題

方針

点数が更新されたとき、その時点で最も高い得点を持つチームの番号が分かればよいので、セグメント木を使います。クエリは全区間を対象とするので、根の値が最も高い得点を持つチームの番号となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

class SegmentTree {
private:
    int n;
    vector<ll> node;
    vector<int> idx;
    ll INF = (1ll << 31) - 1;
public:
    SegmentTree(int N) {
        n = 1;
        while (n < N) n *= 2;
        node.resize(2 * n - 1, -INF);
        idx.resize(2 * n - 1, -1);
        for (int i = 0; i < N; i++) {
            node[i + n - 1] = 0;
            idx[i + n - 1] = i;
        }
        for (int i = n - 2; i >= 0; i--) {
            node[i] = max(node[2 * i + 1], node[2 * i + 2]);
            if (node[2 * i + 1] >= node[2 * i + 2]) {
                idx[i] = idx[2 * i + 1];
            } else {
                idx[i] = idx[2 * i + 2];
            }
        }

    }

    void update(int i, ll x) {
        i += (n - 1);
        node[i] += x;
        while (i > 0) {
            i = (i - 1) / 2;
            int l = 2 * i + 1;
            int r = 2 * i + 2;
            node[i] = max(node[l], node[r]);
            if (node[l] >= node[r]) {
                idx[i] = idx[l];
            } else {
                idx[i] = idx[r];
            }
        }
    }

    int query() {
        return idx[0];
    }

    void disp() {
        for (int i = 0; i < 2 * n - 1; i++) {
            cout << idx[i] << " " << node[i] << "\n";
        }
    }

};

int main() {
    int N, R, L;
    cin >> N >> R >> L;
    int k = 0;
    ll v[N]{};
    SegmentTree st(N);
    int n = 1;
    while (n < N) n *= 2;
    int d[R], t[R], x[R];
    for (int i = 0; i < R; i++) {
        cin >> d[i] >> t[i] >> x[i];
        d[i]--; 
    }
    
    for (int i = 0; i < R; i++) {
        int idx = st.query();
        v[idx] += t[i] - k;
        k = t[i];
        st.update(d[i], x[i]);
    }

    v[st.query()] += L - k;
    int ans = 0;
    for (int i = N - 1; i >= 0; i--) {
        if (v[ans] <= v[i]) {
            ans = i;
        }
    }
    cout << ans + 1 << "\n";
    
    return 0;
}