解法1.セグメント木(区間更新点クエリ)
番目の竹が伐採されるイベントの時刻を とする.このとき,各イベントで得られる得点は, となる. 番目の竹が最終得点に寄与する部分は,
となるので,最終的に得られる得点の総和は,各竹が伐採される最も遅い時刻の総和である.
各竹に対して伐採される最も遅い時刻をセグメント木の値として持ち,各イベントでその値を区間で更新する.すべてのイベント終了後のセグメント木の値の総和が答えとなる.
計算時間:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<typename T>
struct SegmentTree {
std::size_t sz;
std::vector<T> d;
SegmentTree(std::size_t n = 0) {
for (sz = 1; sz < n; ) sz <<= 1;
d.resize(2 * sz);
}
void modify(int l, int r, T value) {
for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
if (l & 1) { d[l] = max(d[l], value); ++l; }
if (r & 1) { --r; d[r] = max(d[r], value); }
}
}
T query(int p) {
T res = 0;
for (p += sz; p > 0; p >>= 1) res = max(res, d[p]);
return res;
}
};
int main() {
cin.tie(0); ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
SegmentTree<int> seg(n);
for (int i = 0, l, r, t; i < m; ++i) {
cin >> t >> l >> r;
seg.modify(l - 1, r, t);
}
ll res = 0;
for (int i = 0; i < n; ++i)
res += seg.query(i);
cout << res << endl;
return 0;
}
解法2. set
関数
イベントを逆順で行うことを考える.初めて伐採される竹はそのイベントでの時刻が得点となり,それ以降のイベントでは答えに寄与することはない.したがって, 番目のイベントで得られる得点は,まだ伐採されていない 以上 以下の番号の竹の数を とすると, となる.C++ の set
の要素をまだ伐採されていない竹の番号とすることによってこのクエリを高速に行うことができる.
計算時間:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
cin.tie(0); ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
vector<ll> t(m), l(m), r(m);
for (int i = 0; i < n; ++i)
cin >> t[i] >> l[i] >> r[i];
set<int> take;
for (int i = 1; i <= n; ++i) take.insert(i);
ll res = 0;
for (int i = m - 1; 0 <= i; --i) {
const auto iter_l = take.lower_bound(l[i]);
const auto iter_r = take.upper_bound(r[i]);
res += t[i] * distance(iter_l, iter_r);
take.erase(iter_l, iter_r);
}
cout << res << endl;
return 0;
}