結果
問題 | No.489 株に挑戦 |
ユーザー |
|
提出日時 | 2017-02-24 23:26:29 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 44 ms / 1,000 ms |
コード長 | 3,089 bytes |
コンパイル時間 | 1,267 ms |
コンパイル使用メモリ | 93,304 KB |
実行使用メモリ | 18,944 KB |
最終ジャッジ日時 | 2024-07-19 23:06:31 |
合計ジャッジ時間 | 2,593 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
コンパイルメッセージ
main.cpp: In static member function ‘static int SparseTable<T, BiOp>::top_bit(int) [with T = long long int; BiOp = mymax]’: main.cpp:71:7: warning: ‘v’ is used uninitialized [-Wuninitialized] 71 | c = *(const int *) &v; // OR, for portability: memcpy(&c, &v, sizeof c); | ~~^~~~~~~~~~~~~~~~~~~ main.cpp:68:17: note: ‘v’ declared here 68 | const float v = t; // find int(log2(v)), where v > 0.0 && finite(v) && isnormal(v) | ^
ソースコード
#include <algorithm>#include <bitset>#include <cassert>#include <cctype>#include <cmath>#include <cstdio>#include <cstdlib>#include <cstring>#include <ctime>#include <deque>#include <functional>#include <iomanip>#include <iostream>#include <list>#include <map>#include <numeric>#include <queue>#include <set>#include <sstream>#include <stack>#include <string>#include <utility>#include <vector>#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)using namespace std;typedef long long int ll;typedef vector<int> VI;typedef vector<ll> VL;typedef pair<int, int> PI;const ll mod = 1e9 + 7;/** Sparse Table.* BiOp should be the type of a binary operator which is* associative, commutative and idempotent.* (For example, min and gcd satisfy them.)* Header Requirement: vector, cassert* Verified by: AtCoder ARC023 D (http://arc023.contest.atcoder.jp/submissions/960757)*/template<class T, class BiOp>class SparseTable {private:BiOp biop;std::vector<std::vector<T> > st;void create_sparse_table(int n, const std::vector<T> &lcp) {int h = 1;while ((1 << h) < n) {++h;}st = std::vector<std::vector<T> >(h + 1, std::vector<T>(n));for (int i = 0; i < n; ++i) {st[0][i] = lcp[i];}for (int j = 1; j <= h; ++j) {for (int i = 0; i <= n - (1 << j); ++i) {st[j][i] = biop(st[j - 1][i], st[j - 1][i + (1 << (j-1))]);}}}/** Reference: https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogFloat* Please be aware that it only works well in case of 1 <= t <= 2^24.*/static int top_bit(int t) {const float v = t; // find int(log2(v)), where v > 0.0 && finite(v) && isnormal(v)int c; // 32-bit int c gets the result;c = *(const int *) &v; // OR, for portability: memcpy(&c, &v, sizeof c);return (c >> 23) - 127;}public:/** Initializes this sparse table. O(n log n) where n = ary.size().*/SparseTable(BiOp biop, const std::vector<T> &ary): biop(biop) {create_sparse_table(ary.size(), ary);}/** Computes biop(ary[f], ary[f+1], ..., ary[s]). O(1).* Note: the interval is inclusive.*/T query(int f, int s) const {assert (f <= s);int diff = top_bit(s + 1 - f);return biop(st[diff][f], st[diff][s + 1 - (1 << diff)]);}};struct mymax {ll operator()(ll x, ll y) const {return max(x, y);}};int main(void){int n, d;ll k;cin >> n >> d >> k;VL x(n);REP(i, 0, n) {cin >> x[i];}SparseTable<ll, mymax> spt(mymax(), x);ll ma = 0;int mini1 = -1;REP(i, 0, n) {ll a = x[i];ll y = spt.query(i, min(i + d, n - 1));if (y <= a) { continue; }ll t = y - a;if (ma < t) {ma = t;mini1 = i;}}if (ma == 0) {cout << 0 << endl;return 0;}cout << ma * k << endl;cout << mini1 << " ";int mini2 = -1;REP(i, mini1, min(mini1 + d + 1, n)) {if (ma + x[mini1] == x[i]) {mini2 = i;break;}}assert (mini2 >= 0);cout << mini2 << endl;}