結果

問題 No.489 株に挑戦
ユーザー koba-e964koba-e964
提出日時 2017-02-24 23:26:29
言語 C++11
(gcc 11.4.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 35 ms
14,848 KB
testcase_01 AC 23 ms
10,368 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 1 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 4 ms
5,376 KB
testcase_16 AC 33 ms
16,512 KB
testcase_17 AC 6 ms
5,376 KB
testcase_18 AC 20 ms
10,496 KB
testcase_19 AC 16 ms
8,960 KB
testcase_20 AC 40 ms
16,640 KB
testcase_21 AC 11 ms
6,144 KB
testcase_22 AC 5 ms
5,376 KB
testcase_23 AC 25 ms
11,008 KB
testcase_24 AC 44 ms
18,816 KB
testcase_25 AC 2 ms
5,376 KB
testcase_26 AC 43 ms
18,816 KB
testcase_27 AC 42 ms
18,816 KB
testcase_28 AC 1 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
testcase_30 AC 44 ms
18,944 KB
testcase_31 AC 42 ms
18,944 KB
testcase_32 AC 24 ms
11,136 KB
testcase_33 AC 42 ms
18,176 KB
testcase_34 AC 37 ms
16,256 KB
testcase_35 AC 16 ms
8,064 KB
testcase_36 AC 7 ms
5,376 KB
testcase_37 AC 24 ms
11,136 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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