結果
問題 | No.2808 Concentration |
ユーザー | silv723 |
提出日時 | 2024-07-09 23:01:23 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,837 bytes |
コンパイル時間 | 2,791 ms |
コンパイル使用メモリ | 217,516 KB |
実行使用メモリ | 145,544 KB |
最終ジャッジ日時 | 2024-07-09 23:02:12 |
合計ジャッジ時間 | 43,998 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 565 ms
57,040 KB |
testcase_04 | AC | 202 ms
23,000 KB |
testcase_05 | AC | 8 ms
5,376 KB |
testcase_06 | AC | 620 ms
67,788 KB |
testcase_07 | AC | 826 ms
78,568 KB |
testcase_08 | AC | 515 ms
41,416 KB |
testcase_09 | AC | 1,121 ms
113,096 KB |
testcase_10 | AC | 171 ms
19,108 KB |
testcase_11 | AC | 877 ms
91,580 KB |
testcase_12 | AC | 1,003 ms
104,492 KB |
testcase_13 | TLE | - |
testcase_14 | AC | 1,027 ms
112,612 KB |
testcase_15 | AC | 595 ms
62,392 KB |
testcase_16 | AC | 874 ms
89,600 KB |
testcase_17 | AC | 885 ms
93,028 KB |
testcase_18 | WA | - |
testcase_19 | AC | 505 ms
55,936 KB |
testcase_20 | AC | 1,024 ms
106,256 KB |
testcase_21 | AC | 619 ms
61,120 KB |
testcase_22 | AC | 1,345 ms
124,268 KB |
testcase_23 | AC | 1,351 ms
133,756 KB |
testcase_24 | AC | 1,212 ms
116,988 KB |
testcase_25 | AC | 1,072 ms
109,692 KB |
testcase_26 | AC | 1,012 ms
103,416 KB |
testcase_27 | AC | 983 ms
99,960 KB |
testcase_28 | AC | 947 ms
98,936 KB |
testcase_29 | AC | 1,180 ms
117,368 KB |
testcase_30 | AC | 1,044 ms
111,356 KB |
testcase_31 | AC | 1,055 ms
104,064 KB |
testcase_32 | AC | 1,067 ms
115,072 KB |
testcase_33 | AC | 1,209 ms
123,644 KB |
testcase_34 | AC | 1,097 ms
119,676 KB |
testcase_35 | AC | 1,016 ms
103,544 KB |
testcase_36 | AC | 1,066 ms
109,948 KB |
testcase_37 | AC | 1,077 ms
114,560 KB |
testcase_38 | AC | 1,180 ms
123,768 KB |
testcase_39 | AC | 1,322 ms
128,160 KB |
testcase_40 | AC | 1,174 ms
115,192 KB |
testcase_41 | AC | 1,083 ms
104,524 KB |
testcase_42 | AC | 1,085 ms
106,700 KB |
testcase_43 | AC | 2 ms
5,376 KB |
testcase_44 | AC | 1 ms
5,376 KB |
testcase_45 | AC | 1 ms
5,376 KB |
testcase_46 | AC | 2 ms
5,376 KB |
testcase_47 | AC | 2 ms
5,376 KB |
testcase_48 | AC | 2 ms
5,376 KB |
testcase_49 | AC | 2 ms
5,376 KB |
testcase_50 | AC | 2 ms
5,376 KB |
testcase_51 | AC | 2 ms
5,376 KB |
testcase_52 | AC | 1 ms
5,376 KB |
ソースコード
#include<bits/stdc++.h>using namespace std;template <class S, S (*op)(S, S), S (*e)()> class dynamic_segtree {public:dynamic_segtree(size_t n) : n(n), root(nullptr) {}void set(size_t p, S x) {assert(p < n);set(root, 0, n, p, x);}S get(size_t p) const {assert(p < n);return get(root, 0, n, p);}S prod(size_t l, size_t r) const {assert(l <= r && r <= n);return prod(root, 0, n, l, r);}S all_prod() const { return root ? root->product : e(); }void reset(size_t l, size_t r) {assert(l <= r && r <= n);return reset(root, 0, n, l, r);}template <bool (*f)(S)> size_t max_right(size_t l) const {return max_right(l, [](S x) { return f(x); });}template <class F> size_t max_right(size_t l, const F& f) const {assert(l <= n);S product = e();assert(f(product));return max_right(root, 0, n, l, f, product);}template <bool (*f)(S)> size_t min_left(size_t r) const {return min_left(r, [](S x) { return f(x); });}template <class F> size_t min_left(size_t r, const F& f) const {assert(r <= n);S product = e();assert(f(product));return min_left(root, 0, n, r, f, product);}private:struct node;using node_ptr = std::unique_ptr<node>;struct node {size_t index;S value, product;node_ptr left, right;node(size_t index, S value): index(index),value(value),product(value),left(nullptr),right(nullptr) {}void update() {product = op(op(left ? left->product : e(), value),right ? right->product : e());}};const size_t n;node_ptr root;void set(node_ptr& t, size_t a, size_t b, size_t p, S x) const {if (!t) {t = std::make_unique<node>(p, x);return;}if (t->index == p) {t->value = x;t->update();return;}size_t c = (a + b) >> 1;if (p < c) {if (t->index < p) std::swap(t->index, p), std::swap(t->value, x);set(t->left, a, c, p, x);} else {if (p < t->index) std::swap(p, t->index), std::swap(x, t->value);set(t->right, c, b, p, x);}t->update();}S get(const node_ptr& t, size_t a, size_t b, size_t p) const {if (!t) return e();if (t->index == p) return t->value;size_t c = (a + b) >> 1;if (p < c) return get(t->left, a, c, p);else return get(t->right, c, b, p);}S prod(const node_ptr& t, size_t a, size_t b, size_t l, size_t r) const {if (!t || b <= l || r <= a) return e();if (l <= a && b <= r) return t->product;size_t c = (a + b) >> 1;S result = prod(t->left, a, c, l, r);if (l <= t->index && t->index < r) result = op(result, t->value);return op(result, prod(t->right, c, b, l, r));}void reset(node_ptr& t, size_t a, size_t b, size_t l, size_t r) const {if (!t || b <= l || r <= a) return;if (l <= a && b <= r) {t.reset();return;}size_t c = (a + b) >> 1;reset(t->left, a, c, l, r);reset(t->right, c, b, l, r);t->update();}};using S = long long;S op(S a, S b){return max(a, b);}S e(){return 0;};int main(){long long n, s, h;cin >> n >> s >> h;vector<int> x(n), y(n), z(n);for(int i = 0; i < n; i++){cin >> x[i] >> y[i] >> z[i];}vector<long long> ch;for(int i = 0; i < n; i++){ch.push_back(x[i]);ch.push_back(y[i]);ch.push_back(x[i]-s);ch.push_back(y[i]-s);ch.push_back(x[i]-h);ch.push_back(y[i]-h);ch.push_back(x[i]+s+h);ch.push_back(y[i]+s+h);ch.push_back(x[i]+s-h);ch.push_back(y[i]+s-h);ch.push_back(x[i]-s+h);ch.push_back(y[i]-s+h);ch.push_back(x[i]-s-h);ch.push_back(y[i]-s-h);}sort(ch.begin(), ch.end());dynamic_segtree<S, op, e> d(1LL<<31);int pz = 3;if(n < 150000) pz = 4;if(n < 100000) pz = 5;if(n < 50000) pz = 8;vector<pair<int, int>> p(pz);vector<long long> sum(pz);for(auto a:ch){if(a < 0) continue;if(a >= (1LL<<31)) continue;long long cnt = 0;for(int i = 0; i < pz; i++){while(a-(s+h)*(i+1) > x[p[i].first] && p[i].first < n){sum[i] -= z[p[i].first];p[i].first++;}while(a-(s+h)*(i+1)+s >= y[p[i].second] && p[i].second < n){sum[i] += z[p[i].second];p[i].second++;}cnt += sum[i];long long u = d.prod(0, max(0LL, a-(s+h)*(i+1))) + cnt;d.set(a, max(d.get(a), u));}}cout << d.prod(0, 1LL<<31) << endl;}