結果

問題 No.335 門松宝くじ
コンテスト
ユーザー t98slider
提出日時 2023-03-21 22:03:46
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 21 ms / 2,000 ms
コード長 2,339 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,062 ms
コンパイル使用メモリ 184,912 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-18 14:32:03
合計ジャッジ時間 2,534 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

template<class T,T (*op)(T, T),T (*e)()> struct SparseTable {
    vector<vector<T>> table;
    vector<int> lookup;
    int LOGV=0, _n;
    SparseTable(const vector<T> &v) {
        _n=v.size();
        while(_n>>LOGV)LOGV++;
        table.assign(LOGV,vector<T>(_n));
        lookup.resize(_n+1);
        for(int i = 0; i < _n; i++) table[0][i] = v[i];
        for(int i = 1; i < LOGV; i++) {
            for(int j = 0; j + (1 << i) <= _n; j++) {
                table[i][j] = op(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
            }
        }
        lookup[1] = 0;
        for(int i = 2; i < lookup.size(); i++) {
            lookup[i] = lookup[i >> 1] + 1;
        }
    }
    T prod(const int l, const int r){
        assert(0 <= l && l <= r && r <= _n);
        if(l==r)return e();
        int b = lookup[r - l];
        return op(table[b][l],table[b][r - (1<<b)]);
    }
};

int op1(int lhs, int rhs){return max(lhs, rhs);}
int op2(int lhs, int rhs){return min(lhs, rhs);}
int e1(){return -1;}
int e2(){return 1 << 30;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    SparseTable<int, op1, e1> st1(vector<int>(1));
    SparseTable<int, op2, e2> st2(vector<int>(1));
    vector<pair<int,int>> b(m);
    auto f = [&](int l, int r){
        int mx = 0, coef = max(a[l], a[r]);
        if(st1.prod(0, l) > a[l] && a[l] < a[r]) mx = max(mx, max(st1.prod(0, l), coef));
        if(st2.prod(0, l) < a[l] && a[l] > a[r]) mx = max(mx, coef);
        if(a[l] > st2.prod(l + 1, r) && st2.prod(l + 1, r) < a[r]) mx = max(mx, coef);
        if(a[l] < st1.prod(l + 1, r) && st1.prod(l + 1, r) > a[r]) mx = max(mx, st1.prod(l + 1, r));
        if(a[l] > a[r] && a[r] < st1.prod(r, n)) mx = max(mx, max(st1.prod(r, n), coef));
        if(a[l] < a[r] && a[r] > st2.prod(r, n)) mx = max(mx, coef);
        return mx;
    };
    for(int i = 0; i < m; i++){
        for(auto &&v: a) cin >> v;
        st1 = SparseTable<int, op1, e1>(a);
        st2 = SparseTable<int, op2, e2>(a);
        b[i] = {0, -i};
        for(int j = 0; j < n; j++){
            for(int k = j + 1; k < n; k++){
                b[i].first += f(j, k);
            }
        }
    }
    sort(b.rbegin(), b.rend());
    cout << -b[0].second << '\n';
}
0