結果

問題 No.992 最長増加部分列の数え上げ
ユーザー ningenMeningenMe
提出日時 2020-02-20 20:10:17
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 379 ms / 2,000 ms
コード長 6,451 bytes
コンパイル時間 1,029 ms
コンパイル使用メモリ 90,240 KB
実行使用メモリ 34,944 KB
最終ジャッジ日時 2024-04-17 06:29:15
合計ジャッジ時間 12,880 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 118 ms
16,512 KB
testcase_05 AC 82 ms
12,160 KB
testcase_06 AC 155 ms
18,508 KB
testcase_07 AC 106 ms
15,616 KB
testcase_08 AC 52 ms
9,600 KB
testcase_09 AC 107 ms
15,872 KB
testcase_10 AC 155 ms
18,688 KB
testcase_11 AC 202 ms
21,504 KB
testcase_12 AC 33 ms
7,296 KB
testcase_13 AC 98 ms
15,196 KB
testcase_14 AC 99 ms
15,172 KB
testcase_15 AC 34 ms
7,424 KB
testcase_16 AC 325 ms
32,712 KB
testcase_17 AC 49 ms
9,600 KB
testcase_18 AC 91 ms
15,232 KB
testcase_19 AC 186 ms
21,376 KB
testcase_20 AC 362 ms
34,944 KB
testcase_21 AC 363 ms
34,816 KB
testcase_22 AC 370 ms
34,816 KB
testcase_23 AC 370 ms
34,944 KB
testcase_24 AC 354 ms
34,816 KB
testcase_25 AC 338 ms
34,816 KB
testcase_26 AC 379 ms
34,944 KB
testcase_27 AC 374 ms
34,788 KB
testcase_28 AC 359 ms
34,800 KB
testcase_29 AC 368 ms
34,816 KB
testcase_30 AC 218 ms
32,696 KB
testcase_31 AC 219 ms
32,748 KB
testcase_32 AC 218 ms
32,768 KB
testcase_33 AC 217 ms
32,692 KB
testcase_34 AC 218 ms
32,636 KB
testcase_35 AC 218 ms
32,640 KB
testcase_36 AC 217 ms
32,896 KB
testcase_37 AC 216 ms
32,680 KB
testcase_38 AC 222 ms
32,632 KB
testcase_39 AC 219 ms
32,768 KB
testcase_40 AC 221 ms
32,640 KB
testcase_41 AC 223 ms
32,692 KB
testcase_42 AC 221 ms
32,776 KB
testcase_43 AC 221 ms
32,640 KB
testcase_44 AC 221 ms
32,896 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>

using namespace std;
using ll = long long;
const ll MOD = (ll)1e9 + 7;

template<class Operator> class SegmentTree {
    Operator Op;                            //Operator 演算子、型、単位元を持つ
    using typeNode = decltype(Op.unitNode); //nodeの型
    size_t length;                          //セグメント木の最下段の要素の数(vectorの要素の数を超える2べきの数)
    vector<typeNode> node;                  //ノード
    
public:
    
    //unitで初期化
    SegmentTree(const size_t num){
        for (length = 1; length < num; length *= 2);
        node.resize(2 * length, Op.unitNode);
    }
    
    //vectorで初期化
    SegmentTree(const vector<typeNode> & vec){
        for (length = 1; length < vec.size(); length *= 2);
        node.resize(2 * length, Op.unitNode);
        for (int i = 0; i < vec.size(); ++i) node[i + length] = vec[i];
        for (int i = length - 1; i >= 0; --i) node[i] = Op.funcNode(node[(i<<1)+0],node[(i<<1)+1]);
    }
    
    //同じinitで初期化
    SegmentTree(const size_t num, const typeNode init) {
        for (length = 1; length < num; length *= 2);
        node.resize(2 * length, init);
    }
    
    //idx : 0-indexed
    void update(size_t idx, const typeNode var) {
        if(idx < 0 || length <= idx) return;
        idx += length;
        node[idx] = Op.funcMerge(node[idx],var);
        while(idx >>= 1) node[idx] = Op.funcNode(node[(idx<<1)+0],node[(idx<<1)+1]);
    }
    
    //[l,r)
    typeNode get(int l, int r) {
        if (l < 0 || length <= l || r < 0 || length < r) return Op.unitNode;
        typeNode vl = Op.unitNode, vr = Op.unitNode;
        for(l += length, r += length; l < r; l >>=1, r >>=1) {
            if(l&1) vl = Op.funcNode(vl,node[l++]);
            if(r&1) vr = Op.funcNode(node[--r],vr);
        }
        return Op.funcNode(vl,vr);
    }
    
    void print(){
        cout << "{ " << get(0,1);
        for(int i = 1; i < length; ++i) cout << ", " << get(i,i+1);
        cout << " }" << endl;
        
        for(int i = 1,j = 1; i < 2*length; ++i) {
            cout << node[i] << " ";
            if(i==((1<<j)-1) && ++j) cout << endl;
        }
    }
    
};

template<class typeNode> struct nodeMaxRangeMerge {
    typeNode unitNode = {0,0};
    typeNode funcNode(typeNode l,typeNode r){return (l.first != r.first ? (l.first > r.first ? l : r) : make_pair(l.first,l.second + r.second));}
    typeNode funcMerge(typeNode l,typeNode r){return (l.first != r.first ? (l.first > r.first ? l : r) : r);}
};

template<long long mod> class ModInt {
public:
    long long x;
    ModInt():x(0) {
        // do nothing
    }
    ModInt(long long y) : x(y>=0?(y%mod): (mod - (-y)%mod)%mod) {
        // do nothing
    }
    ModInt &operator+=(const ModInt &p) {
        if((x += p.x) >= mod) x -= mod;
        return *this;
    }
    ModInt &operator+=(const long long y) {
        ModInt p(y);
        if((x += p.x) >= mod) x -= mod;
        return *this;
    }
    ModInt &operator+=(const int y) {
        ModInt p(y);
        if((x += p.x) >= mod) x -= mod;
        return *this;
    }
    ModInt &operator-=(const ModInt &p) {
        if((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }
    ModInt &operator-=(const long long y) {
        ModInt p(y);
        if((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }
    ModInt &operator-=(const int y) {
        ModInt p(y);
        if((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }
    ModInt &operator*=(const ModInt &p) {
        x = (x * p.x % mod);
        return *this;
    }
    ModInt &operator*=(const long long y) {
        ModInt p(y);
        x = (x * p.x % mod);
        return *this;
    }
    ModInt &operator*=(const int y) {
        ModInt p(y);
        x = (x * p.x % mod);
        return *this;
    }
    ModInt &operator/=(const ModInt &p) {
        *this *= p.inv();
        return *this;
    }
    ModInt &operator/=(const long long y) {
        ModInt p(y);
        *this *= p.inv();
        return *this;
    }
    ModInt &operator/=(const int y) {
        ModInt p(y);
        *this *= p.inv();
        return *this;
    }
    ModInt operator=(const int y) {
        ModInt p(y);
        *this = p;
        return *this;
    }
    ModInt operator=(const long long y) {
        ModInt p(y);
        *this = p;
        return *this;
    }
    ModInt operator-() const { return ModInt(-x); }
    ModInt operator++() {
        x++;
        if(x>=mod) x-=mod;
        return *this;
    }
    ModInt operator--() {
        x--;
        if(x<0) x+=mod;
        return *this;
    }
    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
    bool operator==(const ModInt &p) const { return x == p.x; }
    bool operator!=(const ModInt &p) const { return x != p.x; }
    ModInt inv() const {
        int a = x, b = mod, u = 1, v = 0, t;
        while(b > 0) {
            t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        return ModInt(u);
    }
    ModInt pow(long long n) const {
        ModInt ret(1), mul(x);
        while(n > 0) {
            if(n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }
    friend ostream &operator<<(ostream &os, const ModInt &p) {
        return os << p.x;
    }
    friend istream &operator>>(istream &is, ModInt &a) {
        long long t;
        is >> t;
        a = ModInt<mod>(t);
        return (is);
    }
};
using modint = ModInt<MOD>;

int main() {
    int N; cin >> N;
    vector<ll> A(N);
    for(int i = 0; i < N; ++i) cin >> A[i];
    SegmentTree<nodeMaxRangeMerge<pair<int,modint>>> dp(N,{0,0});
    map<ll,vector<int>> mpv;
    for(int i = 0; i < N; ++i) mpv[A[i]].push_back(i);
    for(auto e:mpv) {
        auto v = e.second;
        vector<pair<int,modint>> tmp;
        for(auto r:v) {
            auto m = dp.get(0, r);
            if(m.first) m.first++;
            else m = {1,1};
            tmp.push_back(m);
        }
        for(int i = 0; i < v.size(); ++i) {
            dp.update(v[i], tmp[i]);
        }
    }
    cout << dp.get(0, N).second << endl;
}
0