結果
問題 | No.489 株に挑戦 |
ユーザー |
![]() |
提出日時 | 2020-06-05 01:09:13 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 44 ms / 1,000 ms |
コード長 | 3,203 bytes |
コンパイル時間 | 1,505 ms |
コンパイル使用メモリ | 165,516 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 00:24:02 |
合計ジャッジ時間 | 3,346 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
/*** @FileName a.cpp* @Author kanpurin* @Created 2020.06.05 01:09:06**/#include "bits/stdc++.h"using namespace std;typedef long long ll;template < class Monoid >struct SegmentTree {private:using Func = std::function< Monoid(Monoid, Monoid) >;Func F;Monoid UNITY;int n;std::vector< Monoid > node;public:SegmentTree() {}SegmentTree(int m, const Monoid &val, const Func f, const Monoid &unity) {F = f;UNITY = unity;n = 1;while (n < m) n <<= 1;node.resize(n * 2 - 1, UNITY);if (val != UNITY) {for (int i = 0; i < m; i++) node[i] = val;build();}}SegmentTree(const std::vector< Monoid > &v, const Func f, const Monoid &unity) {F = f;UNITY = unity;int sz = v.size();n = 1;while (n < sz) n <<= 1;node.resize(n * 2 - 1, UNITY);for (int i = 0; i < sz; i++) node[i + n - 1] = v[i];build();}void set(int k, const Monoid &x) {node[n + k - 1] = x;}void build() {for (int i = n - 2; i >= 0; i--) node[i] = F(node[2 * i + 1], node[2 * i + 2]);}void update_query(int x, const Monoid &val) {if (x >= n || x < 0) return;x += n - 1;node[x] = val;while (x > 0) {x = (x - 1) >> 1;node[x] = F(node[2 * x + 1], node[2 * x + 2]);}}/*Monoid query(int a, int b, int k = 0, int l = 0, int r = -1) {if (r < 0) r = n;if (r <= a || b <= l) return UNITY;if (a <= l && r <= b) return node[k];Monoid vl = query(a, b, 2 * k + 1, l, (r - l) / 2 + l);Monoid vr = query(a, b, 2 * k + 2, (r - l) / 2 + l, r);return F(vl, vr);}*/Monoid get_query(int a, int b) {Monoid L = UNITY, R = UNITY;if (a < 0) a = 0;if (b < 0) return UNITY;if (a >= n) return UNITY;if (b >= n) b = n;for (a += n, b += n; a < b; a >>= 1, b >>= 1) {if (a & 1) L = F(L, node[a++ - 1]);if (b & 1) R = F(node[--b - 1], R);}return F(L, R);}Monoid operator[](int x) const {return node[n + x - 1];}int size() {return n;}void print() {for (int i = 0; i < n; i++) {std::cout << i << "\t: " << node[n + i - 1] << std::endl;}}};int main() {int n, d, k;cin >> n >> d >> k;vector< int > x(n);for (int i = 0; i < n; i++) {cin >> x[i];}SegmentTree< int > seg(x, [](int a, int b) { return max(a, b); }, 0);ll ans = 0;int u;for (int i = 0; i < n; i++) {ll t = seg.get_query(i, i + d + 1) - x[i];if (ans < t) {ans = t;u = i;}}if (ans == 0) {cout << 0 << endl;} else {cout << ans * k << endl;for (int i = u + 1; i < min(n,u + d + 1); i++) {if (x[i] - x[u] == ans) {cout << u << " " << i << endl;break;}}}return 0;}