結果
問題 | No.992 最長増加部分列の数え上げ |
ユーザー | 👑 tute7627 |
提出日時 | 2020-02-14 23:18:32 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 133 ms / 2,000 ms |
コード長 | 4,992 bytes |
コンパイル時間 | 2,379 ms |
コンパイル使用メモリ | 192,512 KB |
実行使用メモリ | 33,304 KB |
最終ジャッジ日時 | 2024-10-06 13:18:03 |
合計ジャッジ時間 | 8,029 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 50 ms
13,092 KB |
testcase_05 | AC | 37 ms
10,476 KB |
testcase_06 | AC | 62 ms
15,168 KB |
testcase_07 | AC | 45 ms
12,068 KB |
testcase_08 | AC | 24 ms
7,852 KB |
testcase_09 | AC | 46 ms
12,364 KB |
testcase_10 | AC | 61 ms
15,164 KB |
testcase_11 | AC | 77 ms
18,352 KB |
testcase_12 | AC | 16 ms
6,376 KB |
testcase_13 | AC | 42 ms
11,516 KB |
testcase_14 | AC | 43 ms
11,772 KB |
testcase_15 | AC | 16 ms
6,512 KB |
testcase_16 | AC | 119 ms
26,080 KB |
testcase_17 | AC | 24 ms
7,848 KB |
testcase_18 | AC | 42 ms
11,492 KB |
testcase_19 | AC | 76 ms
18,208 KB |
testcase_20 | AC | 131 ms
28,312 KB |
testcase_21 | AC | 132 ms
28,312 KB |
testcase_22 | AC | 133 ms
28,312 KB |
testcase_23 | AC | 132 ms
28,184 KB |
testcase_24 | AC | 132 ms
28,312 KB |
testcase_25 | AC | 133 ms
28,188 KB |
testcase_26 | AC | 132 ms
28,312 KB |
testcase_27 | AC | 132 ms
28,204 KB |
testcase_28 | AC | 132 ms
28,316 KB |
testcase_29 | AC | 132 ms
28,312 KB |
testcase_30 | AC | 108 ms
32,908 KB |
testcase_31 | AC | 112 ms
31,968 KB |
testcase_32 | AC | 110 ms
32,024 KB |
testcase_33 | AC | 110 ms
32,920 KB |
testcase_34 | AC | 109 ms
32,028 KB |
testcase_35 | AC | 114 ms
32,156 KB |
testcase_36 | AC | 114 ms
32,152 KB |
testcase_37 | AC | 114 ms
32,020 KB |
testcase_38 | AC | 114 ms
32,020 KB |
testcase_39 | AC | 114 ms
32,148 KB |
testcase_40 | AC | 111 ms
33,172 KB |
testcase_41 | AC | 112 ms
33,176 KB |
testcase_42 | AC | 114 ms
33,304 KB |
testcase_43 | AC | 116 ms
33,048 KB |
testcase_44 | AC | 114 ms
33,300 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; #define endl '\n' #define lfs cout<<fixed<<setprecision(10) #define ALL(a) (a).begin(),(a).end() #define ALLR(a) (a).rbegin(),(a).rend() #define spa << " " << #define fi first #define se second #define MP make_pair #define MT make_tuple #define PB push_back #define EB emplace_back #define rep(i,n,m) for(ll i = (n); i < (ll)(m); i++) #define rrep(i,n,m) for(ll i = (m) - 1; i >= (ll)(n); i--) using ll = long long; using ld = long double; const ll MOD = 1e9+7; //const ll MOD = 998244353; const ll INF = 1e18; using P = pair<ll, ll>; template<typename T> bool chmin(T &a,T b){if(a>b){a=b;return true;}else return false;} template<typename T> bool chmax(T &a,T b){if(a<b){a=b;return true;}else return false;} ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});} void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;} void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;} void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;} template<typename T1,typename T2> void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;} template<typename T> void debug(vector<vector<T>>&v,ll h,ll w){for(ll i=0;i<h;i++) {cout<<v[i][0];for(ll j=1;j<w;j++)cout spa v[i][j];cout<<endl;}}; void debug(vector<string>&v,ll h,ll w){for(ll i=0;i<h;i++) {for(ll j=0;j<w;j++)cout<<v[i][j];cout<<endl;}}; template<typename T> void debug(vector<T>&v,ll n){if(n!=0)cout<<v[0]; for(ll i=1;i<n;i++)cout spa v[i];cout<<endl;}; template<typename T> vector<vector<T>>vec(ll x, ll y, T w){ vector<vector<T>>v(x,vector<T>(y,w));return v;} ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;} vector<ll>dx={1,0,-1,0,1,1,-1,-1}; vector<ll>dy={0,1,0,-1,1,-1,1,-1}; template<typename T> vector<T> make_v(size_t a,T b){return vector<T>(a,b);} template<typename... Ts> auto make_v(size_t a,Ts... ts){ return vector<decltype(make_v(ts...))>(a,make_v(ts...)); } ostream &operator<<(ostream &os, pair<ll, ll>&p){ return os << p.first << " " << p.second; } template< int mod > struct ModInt { ll x; ModInt() : x(0) {} ModInt(int64_t 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; } 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(int64_t 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) { int64_t t; is >> t; a = ModInt< mod >(t); return (is); } static int get_mod() { return mod; } }; using modint = ModInt< MOD >; modint pow2(int64_t n, int64_t x){ return modint(n).pow(x); } template<typename T> map<T,ll> compress(vector<T> &t){ sort(ALL(t)); t.erase(unique(ALL(t)),t.end()); map<T, ll> ret; for(ll i=0;i<(ll)t.size();i++) ret[t[i]]=i; return ret; } int main(){ cin.tie(nullptr); ios_base::sync_with_stdio(false); ll res=0,buf=0; bool judge = true; ll n;cin>>n; vector<ll>a(n); rep(i,0,n)cin>>a[i]; vector<ll>val(n); rep(i,0,n)val[i]=a[i]; val.PB(-INF); val.PB(INF); auto mp=compress(val); ll m=mp.size(); vector<ll>dp(n+1,INF); dp[0]=-INF; using PM=pair<ll,modint>; /*auto f=[](PM x,PM y){ return x.fi>x.se; };*/ vector<priority_queue<PM>>que(n+1); vector<modint>sum(n+1); que[0].emplace(-INF,modint(1)); sum[0]+=1; ll mx=0; rep(i,0,n){ ll idx=lower_bound(ALL(dp),a[i])-dp.begin(); while(!que.empty()&&que[idx-1].top().fi>=a[i]){ auto p=que[idx-1].top(); sum[idx-1]-=p.se; que[idx-1].pop(); } que[idx].emplace(a[i],sum[idx-1]); sum[idx]+=sum[idx-1]; dp[idx]=a[i]; chmax(mx,idx); } //debug(dp,n+1); //ep(i,0,n)cout<<sum[mx]<<endl; cout<<sum[mx]<<endl; return 0; }