結果

問題 No.489 株に挑戦
ユーザー koba-e964
提出日時 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)
      |                 ^

ソースコード

diff # 

#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;
}
0