結果

問題 No.335 門松宝くじ
コンテスト
ユーザー kimiyuki
提出日時 2016-02-12 00:09:34
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,096 bytes
コンパイル時間 554 ms
コンパイル使用メモリ 63,796 KB
最終ジャッジ日時 2024-11-14 19:33:27
合計ジャッジ時間 954 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In constructor ‘segment_tree<T>::segment_tree(int, T, F)’:
main.cpp:18:24: error: there are no arguments to ‘log2’ that depend on a template parameter, so a declaration of ‘log2’ must be available [-fpermissive]
   18 |         n = pow(2,ceil(log2(a_n)));
      |                        ^~~~
main.cpp:18:24: note: (if you use ‘-fpermissive’, G++ will accept your code, but allowing the use of an undeclared name is deprecated)
main.cpp: In instantiation of ‘segment_tree<T>::segment_tree(int, T, F) [with F = nc2_expected_value(int, const std::vector<int>&)::<lambda(int, int)>; T = int]’:
main.cpp:51:73:   required from here
main.cpp:18:28: error: ‘log2’ was not declared in this scope
   18 |         n = pow(2,ceil(log2(a_n)));
      |                        ~~~~^~~~~
main.cpp:18:23: error: ‘ceil’ was not declared in this scope
   18 |         n = pow(2,ceil(log2(a_n)));
      |                   ~~~~^~~~~~~~~~~
main.cpp:18:16: error: ‘pow’ was not declared in this scope
   18 |         n = pow(2,ceil(log2(a_n)));
      |             ~~~^~~~~~~~~~~~~~~~~~~
main.cpp: In instantiation of ‘segment_tree<T>::segment_tree(int, T, F) [with F = nc2_expected_value(int, const std::vector<int>&)::<lambda(int, int)>; T = int]’:
main.cpp:52:73:   required from here
main.cpp:18:28: error: ‘log2’ was not declared in this scope
   18 |         n = pow(2,ceil(log2(a_n)));
      |                        ~~~~^~~~~
main.cpp:18:23: error: ‘ceil’ was not declared in this scope
   18 |         n = pow(2,ceil(log2(a_n)));
      |                   ~~~~^~~~~~~~~~~
main.cpp:18:16: error: ‘pow’ was not declared in this scope
   18 |         n = pow(2,ceil(log2(a_n)));
      |             ~~~^~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
typedef long long ll;
using namespace std;
template <typename T> bool setmax(T & l, T const & r) { if (not (l < r)) return false; l = r; return true; }
template <typename T>
struct segment_tree { // on monoid
    int n;
    vector<T> a;
    function<T (T,T)> append; // associative
    T unit;
    template <typename F>
    segment_tree(int a_n, T a_unit, F a_append) {
        n = pow(2,ceil(log2(a_n)));
        a.resize(2*n-1, a_unit);
        unit = a_unit;
        append = a_append;
    }
    void point_update(int i, T z) {
        a[i+n-1] = z;
        for (i = (i+n)/2; i > 0; i /= 2) {
            a[i-1] = append(a[2*i-1], a[2*i]);
        }
    }
    T range_concat(int l, int r) {
        return range_concat(0, 0, n, l, r);
    }
    T range_concat(int i, int il, int ir, int l, int r) {
        if (l <= il and ir <= r) {
            return a[i];
        } else if (ir <= l or r <= il) {
            return unit;
        } else {
            return append(
                    range_concat(2*i+1, il, (il+ir)/2, l, r),
                    range_concat(2*i+2, (il+ir)/2, ir, l, r));
        }
    }
};
bool is_kadomatsu(int a, int b, int c) {
    if (a == b or b == c or c == a) return false;
    if (a < b and b < c) return false;
    if (a > b and b > c) return false;
    return true;
}
ll nc2_expected_value(int n, vector<int> const & e) {
    segment_tree<int> mint(n, n+1, [](int a, int b) { return min(a,b); });
    segment_tree<int> maxt(n,   0, [](int a, int b) { return max(a,b); });
    repeat (i,n) {
        mint.point_update(i, e[i]);
        maxt.point_update(i, e[i]);
    }
    ll result = 0;
    repeat (i,n) {
        repeat_from (j,i+1,n) {
            int l, mn, mx, r;
            if (e[i] < e[j]) {
                l  = maxt.range_concat(0,i);
                mn = mint.range_concat(i+1,j);
                mx = maxt.range_concat(i+1,j);
                r  = mint.range_concat(j+1,n);
            } else {
                l  = mint.range_concat(0,i);
                mn = mint.range_concat(i+1,j);
                mx = maxt.range_concat(i+1,j);
                r  = maxt.range_concat(j+1,n);
            }
            int a = 0;
            if (i   != 0 and is_kadomatsu(l,  e[i], e[j])) setmax(a, max(l,  max(e[i], e[j])));
            if (i+1 != j and is_kadomatsu(e[i], mn, e[j])) setmax(a, max(mn, max(e[i], e[j])));
            if (i+1 != j and is_kadomatsu(e[i], mx, e[j])) setmax(a, max(mx, max(e[i], e[j])));
            if (j != n-1 and is_kadomatsu(e[i], e[j],  r)) setmax(a, max(r,  max(e[i], e[j])));
            result += a;
        }
    }
    return result;
}
int main() {
    int n, m; cin >> n >> m;
    vector<vector<int> > e(m, vector<int>(n));
    repeat (y,m) repeat (x,n) cin >> e[y][x];
    vector<ll> a(m); repeat (y,m) a[y] = nc2_expected_value(n, e[y]);
    cout << max_element(a.begin(), a.end()) - a.begin() << endl;
    return 0;
}
0