結果
問題 | No.844 split game |
ユーザー |
![]() |
提出日時 | 2019-06-28 22:36:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 74 ms / 2,000 ms |
コード長 | 2,106 bytes |
コンパイル時間 | 2,457 ms |
コンパイル使用メモリ | 206,748 KB |
最終ジャッジ日時 | 2025-01-07 05:34:30 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 56 |
ソースコード
#include <bits/stdc++.h> #define rep(i, a, n) for(int i = a; i < n; i++) #define int long long using namespace std; typedef pair<int, int> P; const int mod = 1000000007; const int INF = 1e18; struct S{ int l, r, p; bool operator<(const S &s) const{ if(l == s.l) return r < s.r; return l < s.l; } }; template< typename T, typename E > struct SegmentTree{ using F = function< T(T, T) >; using G = function< T(T, E) >; int sz; vector<T> dat; F f; G g; T t1; SegmentTree(int n, F f, G g, T t1) : f(f), g(g), t1(t1) { sz = 1; while(sz < n) sz *= 2; dat.clear(); dat.resize(2 * sz - 1, t1); } void set(int k, T x) { dat[k + sz - 1] = x; } void build() { for(int k = sz - 2; k >= 0; k--) { dat[k] = f(dat[2 * k + 1], dat[2 * k + 2]); } } void update(int k, E x) { k += sz - 1; dat[k] = g(dat[k], x); while(k > 0) { k = (k - 1) / 2; dat[k] = f(dat[2 * k + 1], dat[2 * k + 2]); } } T query(int a, int b, int k, int l, int r) { if(r <= a || b <= l) return t1; if(a <= l && r <= b) return dat[k]; T vl = query(a, b, k * 2 + 1, l, (l + r) / 2); T vr = query(a, b, k * 2 + 2, (l + r) / 2, r); return f(vl, vr); } T query(int a, int b){ return query(a, b, 0, 0, sz); } T operator[](int k) { return dat[k + sz - 1]; } }; signed main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n, m, a; cin >> n >> m >> a; vector<S> d(m); SegmentTree<int, int> rmq(n + 1, [](int a, int b){ return max(a, b); }, [](int a, int b){ return max(a, b); }, -INF); rep(i, 0, m){ cin >> d[i].l >> d[i].r >> d[i].p; d[i].l--; } rmq.update(0, 0); sort(d.begin(), d.end()); for(int i = 0; i < m; i++){ int tmp = rmq[d[i].l] - a; // cout << i << ' ' << tmp << endl; tmp = max(tmp, rmq.query(0, d[i].l) - 2 * a); if(d[i].r == n) tmp += a; rmq.update(d[i].r, tmp + d[i].p); // rep(j, 0, n + 1){ // cout << rmq[j] << " "; // } // cout << endl; } int ans = rmq.query(0, n + 1); cout << ans << endl; }