結果
問題 | No.844 split game |
ユーザー |
|
提出日時 | 2019-06-28 22:11:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 139 ms / 2,000 ms |
コード長 | 6,996 bytes |
コンパイル時間 | 2,124 ms |
コンパイル使用メモリ | 203,836 KB |
最終ジャッジ日時 | 2025-01-07 05:33:05 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 56 |
ソースコード
#include <bits/stdc++.h>#pragma GCC diagnostic ignored "-Wsign-compare"#pragma GCC diagnostic ignored "-Wsign-conversion"#define NDEBUG#define SHOW(...) static_cast<void>(0)//!===========================================================!////! dP dP dP !////! 88 88 88 !////! 88aaaaa88a .d8888b. .d8888b. .d888b88 .d8888b. 88d888b. !////! 88 88 88ooood8 88' '88 88' '88 88ooood8 88' '88 !////! 88 88 88. ... 88. .88 88. .88 88. ... 88 !////! dP dP '88888P' '88888P8 '88888P8 '88888P' dP !////!===========================================================!//template <typename T>T read(){T v;return std::cin >> v, v;}template <typename T>std::vector<T> readVec(const std::size_t l){std::vector<T> v(l);for (auto& e : v) { std::cin >> e; }return v;}using ld = long double;using uint = unsigned int;using ll = long long;using ull = unsigned long long;constexpr unsigned int MOD = 1000000007;template <typename T>constexpr T INF = std::numeric_limits<T>::max() / 4;template <typename F>constexpr F PI = static_cast<F>(3.1415926535897932385);std::mt19937 mt{std::random_device{}()};template <typename T>bool chmin(T& a, const T& b) { return (a > b ? a = b, true : false); }template <typename T>bool chmax(T& a, const T& b) { return (a < b ? a = b, true : false); }template <typename T>std::vector<T> Vec(const std::size_t n, T v) { return std::vector<T>(n, v); }template <class... Args>auto Vec(const std::size_t n, Args... args) { return std::vector<decltype(Vec(args...))>(n, Vec(args...)); }template <typename T>constexpr T popCount(const T u){#ifdef __has_builtinreturn u == 0 ? T(0) : (T)__builtin_popcountll(u);#elseunsigned long long v = static_cast<unsigned long long>(u);return v = (v & 0x5555555555555555ULL) + (v >> 1 & 0x5555555555555555ULL), v = (v & 0x3333333333333333ULL) + (v >> 2 & 0x3333333333333333ULL), v= (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL, static_cast<T>(v * 0x0101010101010101ULL >> 56 & 0x7f);#endif}template <typename T>constexpr T log2p1(const T u){#ifdef __has_builtinreturn u == 0 ? T(0) : T(64 - __builtin_clzll(u));#elseunsigned long long v = static_cast<unsigned long long>(u);return v = static_cast<unsigned long long>(v), v |= (v >> 1), v |= (v >> 2), v |= (v >> 4), v |= (v >> 8), v |= (v >> 16), v |= (v >> 32),popCount(v);#endif}template <typename T>constexpr T clog(const T v) { return v == 0 ? T(0) : log2p1(v - 1); }template <typename T>constexpr T msbp1(const T v) { return log2p1(v); }template <typename T>constexpr T lsbp1(const T v){#ifdef __has_builtinreturn __builtin_ffsll(v);#elsereturn v == 0 ? T(0) : popCount((v & (-v)) - T(1)) + T(1);#endif}template <typename T>constexpr bool ispow2(const T v) { return popCount(v) == 1; }template <typename T>constexpr T ceil2(const T v) { return v == 0 ? T(1) : T(1) << log2p1(v - 1); }template <typename T>constexpr T floor2(const T v) { return v == 0 ? T(0) : T(1) << (log2p1(v) - 1); }//!===================================================================!////! .d88888b d888888P !////! 88. "' 88 !////! 'Y88888b. .d8888b. .d8888b. 88 88d888b. .d8888b. .d8888b. !////! '8b 88ooood8 88' '88 88 88' '88 88ooood8 88ooood8 !////! d8' .8P 88. ... 88. .88 88 88 88. ... 88. ... !////! Y88888P '88888P' '8888P88 dP dP '88888P' '88888P' !////! .88 !////! d8888P !////!===================================================================!//template <typename ValMonoid>class SegTree{public:using ValType = typename ValMonoid::ValType;SegTree(const std::size_t N, const ValType initial = ValMonoid::id()) : size(N), half(ceil2(size)), val(half << 1, ValMonoid::id()){if (initial != ValMonoid::id()) {std::fill(val.begin() + half, val.end(), initial);for (std::size_t i = half - 1; i >= 1; i--) { up(i); }}}template <typename InIt>SegTree(const InIt first, const InIt last) : size(std::distance(first, last)), half(ceil2(size)), val(half << 1, ValMonoid::id()){std::copy(first, last, val.begin() + half);for (std::size_t i = half - 1; i >= 1; i--) { up(i); }}ValType get(const std::size_t a) const { return assert(a < size), val[a + half]; }void set(std::size_t a, const ValType& v){assert(a < size);val[a += half] = v;while (a >>= 1) { up(a); }}ValType fold(std::size_t L, std::size_t R) const{assert(L < R), assert(R <= size);ValType accl = ValMonoid::id(), accr = ValMonoid::id();for (L += half, R += half; L < R; L >>= 1, R >>= 1) {if (L & 1) { accl = acc(accl, val[L++]); }if (R & 1) { accr = acc(val[--R], accr); }}return acc(accl, accr);}friend std::ostream& operator<<(std::ostream& os, const SegTree& seg){os << "[";for (std::size_t i = seg.half; i < seg.half + seg.size; i++) { os << seg.val[i] << (i + 1 == seg.half + seg.size ? "" : ","); }return (os << "]\n");}private:void up(const std::size_t i) { val[i] = acc(val[i << 1], val[i << 1 | 1]); }const std::size_t size, half;std::vector<ValType> val;const ValMonoid acc{};};//!==================================!////! 8888ba.88ba !////! 88 '8b '8b !////! 88 88 88 .d8888b. dP. .dP !////! 88 88 88 88' '88 '8bd8' !////! dP dP dP '88888P8 dP' 'dP !////!==================================!//template <typename ElemType>struct Max{using ValType = ElemType;ValType operator()(const ValType& a, const ValType& b) const { return std::max(a, b); }static constexpr ValType id() { return std::numeric_limits<ValType>::min(); }};int main(){const int N = read<int>(), M = read<int>();const ll A = read<ll>();std::vector<int> L(M), R(M);std::vector<ll> P(M);for (int i = 0; i < M; i++) { std::cin >> L[i] >> R[i] >> P[i]; }std::vector<int> ind(M);std::iota(ind.begin(), ind.end(), 0);std::sort(ind.begin(), ind.end(), [&](const int i, const int j) { return R[i] == R[j] ? L[i] < L[j] : R[i] < R[j]; });SegTree<Max<ll>> dp(N + 1, -INF<ll>);dp.set(0, A);for (const int i : ind) {const int l = L[i], r = R[i];ll max = std::max(dp.get(l - 1) - A, (l == 1 ? 0 : dp.fold(0, l - 1)) - 2 * A);dp.set(r, std::max(dp.get(r), max + P[i]));}std::cout << std::max({dp.fold(0, N) - A, dp.get(N)}) << std::endl;return 0;}