結果

問題 No.1435 Mmm......
ユーザー carrot46
提出日時 2021-03-19 23:36:52
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 88 ms / 2,000 ms
コード長 5,035 bytes
コンパイル時間 3,410 ms
コンパイル使用メモリ 207,976 KB
最終ジャッジ日時 2025-01-19 19:42:52
ジャッジサーバーID
（参考情報） 		judge4 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0