結果

問題 No.1435 Mmm......
ユーザー carrot46carrot46
提出日時 2021-03-19 23:36:52
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 65 ms / 2,000 ms
コード長 5,035 bytes
コンパイル時間 2,380 ms
コンパイル使用メモリ 216,348 KB
実行使用メモリ 11,884 KB
最終ジャッジ日時 2024-11-19 02:19:46
合計ジャッジ時間 4,454 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 1 ms
5,248 KB
testcase_06 AC 27 ms
10,988 KB
testcase_07 AC 34 ms
11,240 KB
testcase_08 AC 37 ms
11,624 KB
testcase_09 AC 35 ms
11,372 KB
testcase_10 AC 30 ms
11,112 KB
testcase_11 AC 31 ms
11,116 KB
testcase_12 AC 29 ms
10,984 KB
testcase_13 AC 30 ms
10,984 KB
testcase_14 AC 21 ms
7,524 KB
testcase_15 AC 39 ms
11,752 KB
testcase_16 AC 33 ms
11,240 KB
testcase_17 AC 23 ms
7,656 KB
testcase_18 AC 38 ms
11,884 KB
testcase_19 AC 31 ms
11,240 KB
testcase_20 AC 37 ms
11,500 KB
testcase_21 AC 65 ms
11,752 KB
testcase_22 AC 60 ms
11,752 KB
testcase_23 AC 47 ms
11,756 KB
testcase_24 AC 45 ms
11,748 KB
testcase_25 AC 46 ms
11,796 KB
testcase_26 AC 48 ms
11,880 KB
testcase_27 AC 48 ms
11,756 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
//#include <chrono>
#pragma GCC optimize("O3")
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()

using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;

ll N,M,H,W,Q,K,A,B;
string S;
using P = pair<ll, ll>;
const ll INF = (1LL<<60);

template<class T> bool chmin(T &a, const T b){
    if(a > b) {a = b; return true;}
    else return false;
}
template<class T> bool chmax(T &a, const T b){
    if(a < b) {a = b; return true;}
    else return false;
}
template<class T> void my_printv(std::vector<T> v,bool endline = true){
    if(!v.empty()){
        for(std::size_t i{}; i<v.size()-1; ++i) std::cout<<v[i]<<" ";
        std::cout<<v.back();
    }
    if(endline) std::cout<<std::endl;
}

template<class T> struct sparse_table{
        vector<vector<T> > dbl;
        vector<int> len;
        T f(const T &l, const T &r){
            return max(l, r);
        }
        sparse_table(const vector<T> &v){
            int n = v.size(), k = 1;
            while((1<<k) < n) ++k;
            dbl.resize(k);
            len.resize(n + 1);
            dbl[0] = v;
            reps(i, 1, k) {
                rep(j, n - (1<<i) + 1){
                    dbl[i].push_back(f(dbl[i - 1][j], dbl[i - 1][j + (1<<(i - 1))]));
                }
            }
            Rreps(i, n + 1, 1){
                if((1<<k) > i) --k;
                len[i] = 1<<k;
            }
        }
        T query(int l, int r){
            //[l, r), 0 <= l < r < n
            int k = len[r - l];
            return f(dbl[k][l], dbl[k][r - (1<<k)]);
        }
    };

using tp = tuple<int, int, int>;
const int inf = 1<<30;

template <class T> class SEGTREE {
    unsigned int n;
    T dflt;
    vector<T> dat;

    static T op(const T &a, const T &b) {
        auto [m1a, m2a, Ma] = a;
        auto [m1b, m2b, Mb] = b;
        if(m1a < m1b) return {m1a, min(m2a, m1b), max(Ma, Mb)};
        else return {m1b, min(m1a, m2b), max(Ma, Mb)};
    }

    bool f(const T &a){
        return get<2>(a) > get<0>(a) + get<1>(a);
    }

public:
    SEGTREE(unsigned long _n, T _a) : n(1), dflt(_a) {
        while (n < _n) {n *= 2;}
        dat.resize(n * 2, dflt);
    }

    void update(unsigned int k, T a) {
        k += n;
        dat[k] = a;
        while (k > 0) {
            k >>= 1;
            dat[k] = op(dat[k<<1], dat[(k<<1)|1]);
        }
    }

    void init(vector<T> &v) {
        for (int i = 0; i < (int)v.size(); ++i) dat[i + n] = v[i];
        for (int i = n - 1; i >= 1; --i) {
            dat[i] = op(dat[i * 2], dat[i * 2 + 1]);
        }
    }

    T query(unsigned int l, unsigned int r) {
        T res_left = dflt, res_right = dflt;
        l += n; r += n;
        for ( ; l < r; l >>= 1, r >>= 1){
            if(l&1){
                res_left = op(res_left, dat[l]);
                if((++l) == r) break;
            }
            if(r&1){
                res_right = op(dat[r ^ 1], res_right);
            }
        }
        return op(res_left, res_right);
    }

    unsigned int max_right_search(unsigned int id, T &total){
        while(id < n) {
            id <<= 1;
            if(!f(op(total, dat[id]))){
                total = op(total, dat[id]);
                id |= 1;
            }
        }
        return id - n;
    }

    unsigned int max_right(unsigned int l, unsigned int r){
        //定義：op( dat[i], ..., dat[j - 1] ) = false
        //      op( dat[i], ..., dat[j] ) = true      となるjを返す(単調性を仮定)
        //op = maxの場合、[l, r)内のindexであるjであって、query(l, j) < a <= query(l, j + 1)なるものを求める
        //つまり、j >= l かつ dat[j] >= a である最小の数jを求める
        l += n;
        stack<unsigned int> right_id;
        T total(dflt);
        for (unsigned int tr = r + n ; l < tr; l >>= 1, tr >>= 1){
            if(l&1){
                if(f(op(total, dat[l]))) return max_right_search(l, total);
                total = op(total, dat[l]);
                if((++l) == tr) break;
            }
            if(tr&1) right_id.push(tr ^ 1);
        }
        while(!right_id.empty()){
            int id = right_id.top(); right_id.pop();
            if(f(op(total, dat[id]))) return max_right_search(id, total);
            total = op(total, dat[id]);
        }
        return r;
    }

    //単項にアクセスする[]だが、書き換え厳禁
    //一応後でinitすれば書き換えてもよさそうだが…
    ll &operator[](int k) { return dat[k + n]; }
};

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin>>N;
    vector<tp> v;
    rep(i, N) {
        int a;
        cin>>a;
        v.emplace_back(a, inf, a);
    }
    SEGTREE<tp> seg(N, {inf, inf, -inf});
    seg.init(v);

    ll res = N * (N - 1) / 2;
    rep(i, N - 1){
        res -= N - seg.max_right(i, N);
    }
    cout<<res<<endl;
}
0