結果
問題 | No.844 split game |
ユーザー |
|
提出日時 | 2020-12-20 17:04:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,318 bytes |
コンパイル時間 | 1,593 ms |
コンパイル使用メモリ | 136,216 KB |
最終ジャッジ日時 | 2025-01-17 04:52:47 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 31 WA * 25 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <cmath>#include <queue>#include <string>#include <map>#include <set>#include <stack>#include <tuple>#include <deque>#include <array>#include <numeric>#include <bitset>#include <iomanip>#include <cassert>#include <chrono>#include <random>#include <limits>#include <iterator>#include <functional>#include <sstream>#include <fstream>#include <complex>#include <cstring>#include <unordered_map>using namespace std;using ll = long long;using P = pair<int, int>;constexpr int INF = 1001001001;constexpr int mod = 1000000007;// constexpr int mod = 998244353;template<class T>inline bool chmax(T& x, T y){if(x < y){x = y;return true;}return false;}template<class T>inline bool chmin(T& x, T y){if(x > y){x = y;return true;}return false;}template<typename Monoid>struct SegmentTree{using F = function<Monoid(Monoid, Monoid)>;int sz;vector<Monoid> seg;const F f;const Monoid M1;SegmentTree(const F f, const Monoid& M1) : f(f), M1(M1) {}SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {sz = 1;while(sz < n) sz <<= 1;seg.assign(2 * sz, M1);}void resize(int n){sz = 1;while(sz < n) sz <<= 1;seg.assign(2 * sz, M1);}void set(int k, const Monoid &x){seg[k + sz] = x;}void build(){for(int k = sz - 1; k > 0; --k){seg[k] = f(seg[k << 1], seg[k << 1 | 1]);}}void update(int k, const Monoid &x){k += sz;seg[k] = x;while(k >>= 1){seg[k] = f(seg[k << 1], seg[k << 1 | 1]);}}Monoid query(int a, int b){Monoid L = M1, R = M1;for(a += sz, b += sz; a < b; a >>= 1, b >>= 1){if(a & 1) L = f(L, seg[a++]);if(b & 1) R = f(seg[--b], R);}return f(L, R);}Monoid operator[](const int &k) const{return seg[k + sz];}// (type = true) : find_last// (type = false) : find_firsttemplate<typename C>int find_subtree(int a, const C &check, Monoid &M, bool type){while(a < sz){Monoid nxt = type ? f(seg[a << 1 | type], M) : f(M, seg[a << 1 | type]);if(check(nxt)) a = a << 1 | type;else M = nxt, a = 2 * a + 1 - type;}return a - sz;}template<typename C>int find_first(int a, const C &check){Monoid L = M1;if(a <= 0){if(check(f(L, seg[1]))) return find_subtree(1, check, L, false);return -1;}int b = sz;for(a += sz, b += sz; a < b; a >>= 1, b >>= 1){if(a & 1){Monoid nxt = f(L, seg[a]);if(check(nxt)) return find_subtree(a, check, L, false);L = nxt;++a;}}return -1;}template<typename C>int find_last(int b, const C &check){Monoid R = M1;if(b >= sz){if(check(f(seg[1], R))) return find_subtree(1, check, R, true);return -1;}int a = sz;for(b += sz; a < b; a >>= 1, b >>= 1){if(b & 1){Monoid nxt = f(seg[--b], R);if(check(nxt)) return find_subtree(b, check, R, true);R = nxt;}}return -1;}};int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int N, M, A;cin >> N >> M >> A;vector<vector<P>> rights(N);for(int i = 0; i < M; ++i){int l, r, p;cin >> l >> r >> p;rights[l - 1].emplace_back(r, p);}SegmentTree<ll> seg(N + 1, [](ll a, ll b){return max(a, b);}, -1LL);seg.update(0, 0LL);for(int l = 0; l < N; ++l){ll score = seg.query(0, l);if(seg[l] >= score) score = seg[l];else score -= A;for(auto [r, p] : rights[l]){ll next_score = score + p + (r == N ? 0 : -A);if(next_score > seg[r]){seg.update(r, next_score);}}}cout << seg.query(0, N + 1) << endl;return 0;}