結果
問題 | No.992 最長増加部分列の数え上げ |
ユーザー | mugen_1337 |
提出日時 | 2021-03-31 15:51:40 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 347 ms / 2,000 ms |
コード長 | 8,395 bytes |
コンパイル時間 | 2,885 ms |
コンパイル使用メモリ | 227,948 KB |
実行使用メモリ | 19,336 KB |
最終ジャッジ日時 | 2024-05-08 19:02:51 |
合計ジャッジ時間 | 16,716 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 125 ms
6,940 KB |
testcase_05 | AC | 88 ms
6,940 KB |
testcase_06 | AC | 152 ms
6,940 KB |
testcase_07 | AC | 112 ms
6,940 KB |
testcase_08 | AC | 56 ms
6,940 KB |
testcase_09 | AC | 112 ms
6,944 KB |
testcase_10 | AC | 157 ms
6,940 KB |
testcase_11 | AC | 190 ms
6,940 KB |
testcase_12 | AC | 36 ms
6,940 KB |
testcase_13 | AC | 103 ms
6,940 KB |
testcase_14 | AC | 107 ms
6,944 KB |
testcase_15 | AC | 38 ms
6,944 KB |
testcase_16 | AC | 304 ms
8,376 KB |
testcase_17 | AC | 57 ms
6,944 KB |
testcase_18 | AC | 103 ms
6,944 KB |
testcase_19 | AC | 186 ms
6,944 KB |
testcase_20 | AC | 325 ms
8,848 KB |
testcase_21 | AC | 331 ms
9,104 KB |
testcase_22 | AC | 319 ms
8,720 KB |
testcase_23 | AC | 331 ms
8,808 KB |
testcase_24 | AC | 347 ms
8,720 KB |
testcase_25 | AC | 333 ms
8,848 KB |
testcase_26 | AC | 327 ms
8,716 KB |
testcase_27 | AC | 333 ms
8,720 KB |
testcase_28 | AC | 327 ms
8,592 KB |
testcase_29 | AC | 326 ms
8,592 KB |
testcase_30 | AC | 334 ms
19,088 KB |
testcase_31 | AC | 342 ms
19,080 KB |
testcase_32 | AC | 337 ms
19,208 KB |
testcase_33 | AC | 334 ms
19,208 KB |
testcase_34 | AC | 337 ms
19,208 KB |
testcase_35 | AC | 334 ms
19,084 KB |
testcase_36 | AC | 332 ms
19,212 KB |
testcase_37 | AC | 336 ms
19,088 KB |
testcase_38 | AC | 339 ms
19,208 KB |
testcase_39 | AC | 334 ms
19,212 KB |
testcase_40 | AC | 342 ms
19,212 KB |
testcase_41 | AC | 340 ms
19,336 KB |
testcase_42 | AC | 340 ms
19,208 KB |
testcase_43 | AC | 338 ms
19,212 KB |
testcase_44 | AC | 338 ms
19,084 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; #define ALL(x) begin(x),end(x) #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; #define mod 1000000007 using ll=long long; const int INF=1000000000; const ll LINF=1001002003004005006ll; int dx[]={1,0,-1,0},dy[]={0,1,0,-1}; // ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;} template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;} struct IOSetup{ IOSetup(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(12); } } iosetup; template<typename T> ostream &operator<<(ostream &os,const vector<T>&v){ for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" "); return os; } template<typename T> istream &operator>>(istream &is,vector<T>&v){ for(T &x:v)is>>x; return is; } template<typename T> int LongestIncreasingSubsequence(vector<T> v,bool strict=true){ vector<T> lis; for(auto &x:v){ typename vector<T>::iterator ite; if(strict) ite=lower_bound(begin(lis),end(lis),x); else ite=upper_bound(begin(lis),end(lis),x); if(ite==end(lis)) lis.push_back(x); else *ite=x; } return int(lis.size()); } template<ll Mod> struct ModInt{ long long x; ModInt():x(0){} ModInt(long long y):x(y>=0?y%Mod:(Mod-(-y)%Mod)%Mod){} ModInt &operator+=(const ModInt &p){ 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 ModInt &p){ x=(int)(1ll*x*p.x%Mod); return *this; } ModInt &operator/=(const ModInt &p){ (*this)*=p.inverse(); return *this; } ModInt operator-()const{return ModInt(-x);} 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 inverse()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);} static int get_mod(){return Mod;} }; using mint=ModInt<1000000007>; template<typename BitType,int MAXLOG,typename Monoid> struct BinaryTrieMonoid{ private: struct Node{ Node *nxt[2]; Monoid val; Node(Monoid val):nxt{nullptr,nullptr},val(val){} }; Node *root; using F=function<Monoid(Monoid,Monoid)>; F f; const Monoid e; Monoid query(BitType a,BitType b,Node *cur,BitType l,BitType r,int dep,BitType xor_val){ if(a<=l and r<=b) return (cur?cur->val:e); if(dep<0 or b<=l or r<=a or !cur) return e; bool x0=(xor_val>>dep)&1; Monoid L=query(a,b,cur->nxt[x0],l,(l+r)/2,dep-1,xor_val); Monoid R=query(a,b,cur->nxt[x0^1],(l+r)/2,r,dep-1,xor_val); return f(L,R); } void update(Node *cur,Monoid x,BitType bit,int dep){ if(dep==-1){ cur->val=x; return ; } bool go_to=(bit>>dep)&1; if(!cur->nxt[go_to]) cur->nxt[go_to]=new Node(e); update(cur->nxt[go_to],x,bit,dep-1); cur->val=f(cur->nxt[0]?cur->nxt[0]->val:e,cur->nxt[1]?cur->nxt[1]->val:e); return ; } public: BinaryTrieMonoid(F f,const Monoid &e):root(new Node(e)),f(f),e(e){} // fold [l,r) // xor_valを指定したとき,可換じゃない演算だと壊れると思います.多分 Monoid query(BitType l,BitType r,BitType xor_val=0){ return query(l,r,root,0,BitType(1)<<MAXLOG,MAXLOG-1,xor_val); } void update(BitType bit,Monoid x){ update(root,x,bit,MAXLOG-1); } Monoid operator[](const BitType &k){ return query(k,k+1); } }; template<typename Monoid> struct SegmentTree{ using F=function<Monoid(Monoid,Monoid)>; private: int sz; vector<Monoid> seg; Monoid query(int a,int b,int k,int l,int r){ if(a<=l and r<=b) return seg[k]; if(b<=l or r<=a) return M0; Monoid L=query(a,b,2*k,l,(l+r)/2); Monoid R=query(a,b,2*k+1,(l+r)/2,r); return f(L,R); } template<typename C> int find_first(int a,const C &check,Monoid &acc,int k,int l,int r){ if(k>=sz){ acc=f(acc,seg[k]); if(check(acc)) return -1; else return k-sz; } int m=(l+r)/2; if(m<=a) return find_first(a,check,acc,2*k+1,m,r); if(a<=l and check(f(acc,seg[k]))){ acc=f(acc,seg[k]); return -1; } int x=find_first(a,check,acc,2*k+0,l,m); if(x>=0) return x; return find_first(a,check,acc,2*k+1,m,r); } template<typename C> int find_last(int b,const C &check,Monoid &acc,int k,int l,int r){ if(k>=sz){ acc=f(acc,seg[k]); if(check(acc)) return -1; else return k-sz+1;//ここはfalse, +1した位置はtrue } int m=(l+r)/2; if(b<=m) return find_last(b,check,acc,2*k,l,m); if(r<=b and check(f(acc,seg[k]))){ acc=f(acc,seg[k]); return -1; } int x=find_last(b,check,acc,2*k+1,m,r); if(x>=0) return x; return find_last(b,check,acc,2*k,l,m); } public: F f; Monoid M0;// モノイドの元 SegmentTree(int n,F f,Monoid M0):f(f),M0(M0){ sz=1; while(sz<n)sz<<=1; seg.assign(2*sz,M0); } void set(int k,Monoid x){ seg[k+sz]=x; } void build(){ for(int k=sz-1;k>0;k--) seg[k]=f(seg[2*k],seg[2*k+1]); } void update(int k,Monoid x){ k+=sz; seg[k]=x; k>>=1; for(;k;k>>=1) seg[k]=f(seg[2*k],seg[2*k+1]); } Monoid query(int a,int b){ return query(a,b,1,0,sz); } // http://codeforces.com/contest/914/submission/107505449 // max x, check(query(a, x)) = true template<typename C> int find_first(int a,const C &check){ Monoid val=M0; return find_first(a,check,val,1,0,sz); } // http://codeforces.com/contest/914/submission/107505582 // min x, check(query(x, b)) = true template<typename C> int find_last(int b,C &check){ Monoid val=M0; return find_last(b,check,val,1,0,sz); } }; int f(int a,int b){ return max(a,b); } mint g(mint a,mint b){ return a+b; } signed main(){ int n;cin>>n; vector<int> a(n); cin>>a; int M=LongestIncreasingSubsequence(a); { vector<int> v=a; sort(ALL(v)); v.erase(unique(ALL(v)),end(v)); for(auto &x:a) x=lower_bound(ALL(v),x)-begin(v); } vector<int> l(n),r(n); { SegmentTree<int> seg(n,f,0); rep(i,n){ l[i]=seg.query(0,a[i])+1; if(seg.query(a[i],a[i]+1)<l[i]) seg.update(a[i],l[i]); } } { SegmentTree<int> seg(n,f,0); for(int i=n-1;i>=0;i--){ r[i]=seg.query(a[i]+1,n)+1; if(seg.query(a[i],a[i]+1)<r[i]) seg.update(a[i],r[i]); } } vector<int> idx(n,-1); rep(i,n)if(l[i]+r[i]-1==M) idx[i]=l[i]-1; vector<BinaryTrieMonoid<int,18,mint> > segs; rep(i,M){ BinaryTrieMonoid<int,18,mint> tmp(g,0); segs.push_back(tmp); } vector<mint> dp(n,0); rep(i,n){ if(idx[i]<0) continue; if(idx[i]==0) dp[i]=1; else dp[i]=segs[idx[i]-1].query(0,a[i]); mint t=segs[idx[i]].query(a[i],a[i]+1); segs[idx[i]].update(a[i],t+dp[i]); } cout<<segs[M-1].query(0,1<<18)<<endl; return 0; }