[AOJ] No. 0282 プログラミングコンテスト
問題
方針
点数が更新されたとき、その時点で最も高い得点を持つチームの番号が分かればよいので、セグメント木を使います。クエリは全区間を対象とするので、根の値が最も高い得点を持つチームの番号となります。
コード
#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; }
ディスカッション
コメント一覧
まだ、コメントがありません