結果
問題 | No.2229 Treasure Searching Rod (Hard) |
ユーザー | ikefumy |
提出日時 | 2023-02-24 22:23:32 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 5,451 bytes |
コンパイル時間 | 2,451 ms |
コンパイル使用メモリ | 216,660 KB |
実行使用メモリ | 743,552 KB |
最終ジャッジ日時 | 2024-09-13 05:40:49 |
合計ジャッジ時間 | 6,994 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 9 ms
22,272 KB |
testcase_01 | AC | 9 ms
22,272 KB |
testcase_02 | AC | 9 ms
22,144 KB |
testcase_03 | AC | 9 ms
22,272 KB |
testcase_04 | AC | 9 ms
22,144 KB |
testcase_05 | AC | 9 ms
22,144 KB |
testcase_06 | AC | 10 ms
22,276 KB |
testcase_07 | MLE | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
ソースコード
#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define db double #define pii pair<int,int> #define pll pair<ll,ll> #define ti3 tuple<int,int,int> #define int128 __int128_t #define pii128 pair<int128,int128> const int inf = 1 << 30; const ll linf = 1e18; const ll mod = 998244353; const db EPS = 1e-10; const db pi = acos(-1); template<class T> bool chmin(T& x, T y){ if(x > y) { x = y; return true; } else return false; } template<class T> bool chmax(T& x, T y){ if(x < y) { x = y; return true; } else return false; } // overload macro #define CAT( A, B ) A ## B #define SELECT( NAME, NUM ) CAT( NAME, NUM ) #define GET_COUNT( _1, _2, _3, _4, _5, _6 /* ad nauseam */, COUNT, ... ) COUNT #define VA_SIZE( ... ) GET_COUNT( __VA_ARGS__, 6, 5, 4, 3, 2, 1 ) #define VA_SELECT( NAME, ... ) SELECT( NAME, VA_SIZE(__VA_ARGS__) )(__VA_ARGS__) // rep(overload) #define rep( ... ) VA_SELECT(rep, __VA_ARGS__) #define rep2(i, n) for (decay_t<decltype(n)> i = 0; i < n; i++) #define rep3(i, a, b) for (decay_t<decltype(a)> i = a; i < b; i++) #define rep4(i, a, b, c) for (decay_t<decltype(a)> i = a; i < b; i += c) // rrep(overload) #define rrep( ... ) VA_SELECT(rrep, __VA_ARGS__) #define rrep2(i, n) for (decay_t<decltype(n)> i = n - 1; i >= 0; i--) #define rrep3(i, a, b) for (decay_t<decltype(a)> i = b - 1; i >= a; i--) #define rrep4(i, a, b, c) for (decay_t<decltype(a)> i = b - 1; i >= a; i -= c) // for_earh #define fore(e, v) for (auto&& e : v) // vector #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() template<class T, T(* op)(T, T)> struct segment_tree{ int N; T e; vector<T> node; segment_tree(int n, T e) : e(e) { N = 1; while(N < n) N *= 2; node.resize(N * 2 - 1, e); } void update(int i, T x){ i += N - 1; node[i] = x; while(i > 0){ i = (i - 1) / 2; node[i] = op(node[i * 2 + 1], node[i * 2 + 2]); } } T get_val(int a, int b, int k = 0, int l = 0, int r = -1){ if(r == -1) r = N; if(b <= l || r <= a) return e; if(a <= l && r <= b) return node[k]; T vl = get_val(a, b, k * 2 + 1, l, (l + r) / 2); T vr = get_val(a, b, k * 2 + 2, (l + r) / 2, r); return op(vl, vr); } }; template<long long mod> struct modint{ long long num; constexpr modint(long long x = 0) : num((x + mod) % mod) {} constexpr modint &operator += (const modint& rhs){ num = (num + rhs.num) % mod; return *this; } constexpr modint &operator -= (const modint& rhs){ num -= rhs.num; while(num < 0) num += mod; num %= mod; return *this; } constexpr modint &operator *= (const modint& rhs){ num = num * rhs.num % mod; return *this; } constexpr modint &operator /= (modint rhs){ int exp = mod - 2; while(exp > 0){ if(exp % 2){ *this *= rhs; } rhs *= rhs; exp /= 2; } return *this; } constexpr modint operator ++ (){ num = (num + 1) % mod; return *this; } constexpr modint operator ++ (int n){ (void)n; modint tmp = *this; ++(*this); return tmp; } constexpr modint operator -- (){ num = (num + mod - 1) % mod; return *this; } constexpr modint operator -- (int n){ (void)n; const modint tmp = *this; --(*this); return tmp; } void modpow(ll y){ modint tmp = (*this); (*this) = 1; while(y > 0){ if(y % 2){ (*this) *= tmp; } tmp *= tmp; y /= 2; } } constexpr modint operator + (const modint& rhs) const { return modint(*this) += rhs; } constexpr modint operator - (const modint& rhs) const { return modint(*this) -= rhs; } constexpr modint operator * (const modint& rhs) const { return modint(*this) *= rhs; } constexpr modint operator / (const modint& rhs) const { return modint(*this) /= rhs; } friend ostream &operator << (ostream& lhs, const modint& rhs){ return lhs << rhs.num; } friend istream &operator >> (istream& lhs, modint& rhs){ lhs >> rhs.num; return lhs; } }; #define mint modint<mod> mint modpow(mint x, ll y){ if(y == 0) return 1; mint e = modpow(x, y / 2); e = e * e; return e * (y % 2 == 0 ? 1 : x); } mint op(mint a, mint b) { return a + b; } int H, W, K; vector<pii> q[400010]; vector<int> p[400010]; int main() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(20); cin >> H >> W >> K; rep (i, K) { int x, y, v; cin >> x >> y >> v; int rx = x + y, ry = x - y + W; q[rx].emplace_back(ry, v); } rep (i, 1, H + 1) rep (j, 1, W + 1) { int rx = i + j, ry = i - j + W; p[rx].push_back(ry); } mint ans = 0; int N = H + W + 10; segment_tree<mint, op> st(N, (mint)0); rrep (i, 2, H + W + 1) { for (auto& [ry, v] : q[i]) { st.update(ry, st.get_val(ry, ry + 1) + v); } fore (e, p[i]) ans += st.get_val(e, N); } cout << ans << "\n"; }