結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

/**
* @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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0