#776173 (C++17) No.1996 <><

提出ソース

結果

問題	No.1996 <><
ユーザー	eQe
提出日時	2022-07-05 03:01:00
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	84 ms / 2,000 ms
コード長	9,393 bytes
コンパイル時間	11,290 ms
コンパイル使用メモリ	415,504 KB
実行使用メモリ	12,160 KB
最終ジャッジ日時	2024-05-08 18:47:57
合計ジャッジ時間	12,010 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	35 ms 7,680 KB
testcase_12	AC	69 ms 12,160 KB
testcase_13	AC	84 ms 12,160 KB
testcase_14	AC	80 ms 11,776 KB
testcase_15	AC	67 ms 10,624 KB
testcase_16	AC	57 ms 9,856 KB
testcase_17	AC	71 ms 10,624 KB
testcase_18	AC	38 ms 7,552 KB
testcase_19	AC	47 ms 8,320 KB
testcase_20	AC	47 ms 7,936 KB
testcase_21	AC	61 ms 9,856 KB
testcase_22	AC	71 ms 10,880 KB
testcase_23	AC	4 ms 5,376 KB
testcase_24	AC	38 ms 7,552 KB
testcase_25	AC	19 ms 5,376 KB
testcase_26	AC	33 ms 6,784 KB
testcase_27	AC	7 ms 5,376 KB
testcase_28	AC	2 ms 5,376 KB
testcase_29	AC	18 ms 5,376 KB
testcase_30	AC	2 ms 5,376 KB
testcase_31	AC	7 ms 5,376 KB
testcase_32	AC	2 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include<atcoder/all>
#include<bits/stdc++.h>
#include<boost/multiprecision/cpp_int.hpp>
using namespace atcoder;
using namespace std;
using namespace boost::multiprecision;
#define fst first
#define snd second
#define fin(...) exit(pt(__VA_ARGS__))
#define pb(...) pop_back(__VA_ARGS__)
#define eb(...) emplace_back(__VA_ARGS__)
#define ef(...) emplace_front(__VA_ARGS__)
#define elif(...) else if(__VA_ARGS__)
#define wh(...) while(__VA_ARGS__)
#define overload3(a,b,c,d,...) d
#define overload4(a,b,c,d,e,...) e
#define overload5(a,b,c,d,e,f,...) f
#define all1(v) begin(v),end(v)
#define all2(v,b) begin(v),begin(v)+b
#define all3(v,a,b) begin(v)+a,begin(v)+b
#define all(...) overload3(__VA_ARGS__,all3,all2,all1)(__VA_ARGS__)
#define rll1(v) rbegin(v),rend(v)
#define rll2(v,b) rbegin(v),rbegin(v)+b
#define rll3(v,a,b) rbegin(v)+a,rbegin(v)+b
#define rll(...) overload3(__VA_ARGS__,rll3,rll2,rll1)(__VA_ARGS__)
#define rep1(b) for(ll _i=0;_i<(ll)(b);_i++)
#define rep2(i,b) for(ll i=0;i<(ll)(b);i++)
#define rep3(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep4(i,a,b,c) for(ll i=(ll)(a);i<(ll)(b);i+=(ll)(c))
#define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define per1(a) rep(a)
#define per2(i,a) for(ll i=(ll)(a)-1;i>=0;i--)
#define per3(i,a,b) for(ll i=(ll)(a)-1;i>=(ll)(b);i--)
#define per4(i,a,b,c) for(ll i=(ll)(a)-1;i>=(ll)(b);i-=(ll)(c))
#define per(...) overload4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__)
#define fore1(a) rep(sz(a))
#define fore2(a,v) for(auto&&a:v)
#define fore3(a,b,v) for(auto&&[a,b]:v)
#define fore4(a,b,c,v) for(auto&&[a,b,c]:v)
#define fore5(a,b,c,d,v) for(auto&&[a,b,c,d]:v)
#define fore(...) overload5(__VA_ARGS__,fore5,fore4,fore3,fore2,fore1)(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;lin(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;lin(__VA_ARGS__)
#define ST(...) string __VA_ARGS__;lin(__VA_ARGS__)
using ll=long long;
using ld=long double;
using v1=vector<ll>;
using v2=vector<v1>;
using v3=vector<v2>;
using v4=vector<v3>;
using pll=pair<ll,ll>;
using qll=queue<ll>;
using sll=set<ll>;
using msll=multiset<ll>;
using mll=map<ll,ll>;
using mint=modint1000000007;
ll inf=3e18;
ld pi=acosl(-1);
ld eps=1e-10;
template<class T>ll sgn(const T&a){return(a>eps)-(a<-eps);}
template<class T>ll sgn(const T&a,const T&b){return sgn(a-b);}
template<class T>ll sz(const T&a){return size(a);}
template<class T>vector<T>&operator++(vector<T>&v){for(T&x:v)x++;return v;}
template<class T>vector<T>&operator--(vector<T>&v){for(T&x:v)x--;return v;}
template<class T>vector<T>operator++(vector<T>&v,int){vector<T>r=v;++v;return r;}
template<class T>vector<T>operator--(vector<T>&v,int){vector<T>r=v;--v;return r;}
template<class T>vector<T>&operator+=(vector<T>&v,const vector<T>u){copy(all(u),back_inserter(v));return v;}
template<class T>bool operator==(const vector<T>&v,const vector<T>&u){if(sz(v)!=sz(u))return 0;rep(i,sz(v))if(v[i]!=u[i])return 0;return 1;}
template<class T>bool operator!=(const vector<T>&v,const vector<T>&u){return!(v==u);}
template<class T>using max_priority_queue=std::priority_queue<T>;
template<class T>using min_priority_queue=std::priority_queue<T,vector<T>,greater<T>>;
template<class T,class U>bool chmax(T&a,const U&b){return a<b?a=b,1:0;}
template<class T,class U>bool chmin(T&a,const U&b){return a>b?a=b,1:0;}
template<class T>T max(const vector<T>&a){return *max_element(all(a));}
template<class T>T min(const vector<T>&a){return *min_element(all(a));}
template<class...T>constexpr auto max(T...a){return max(initializer_list<common_type_t<T...>>{a...});}
template<class...T>constexpr auto min(T...a){return min(initializer_list<common_type_t<T...>>{a...});}
template<class T,class...A>T gcd(const T&a,const A&...b){return gcd(a,gcd(b...));}
template<class T>T sum(const vector<T>&a){return accumulate(all(a),T(0));}
template<class T>T popcnt(T a){return __builtin_popcountll(a);}
template<class T>ll lbp(const vector<T>&a,const T&b){return lower_bound(all(a),b)-begin(a);}
template<class T>ll ubp(const vector<T>&a,const T&b){return upper_bound(all(a),b)-begin(a);}
template<class T>pair<T,T>mima(const T&a,const T&b){return{min(a,b),max(a,b)};}
template<class T>pair<T,T>mima(const pair<T,T>&p){auto[a,b]=p;return mima(a,b);}
template<class T>T at(const vector<T>&v,const ll&i){ll n=sz(v);return v[(i%n+n)%n];}
template<class T>void sort(vector<T>&v){sort(all(v));}
template<class T,class F>void sort(vector<T>&v,const F&f){sort(all(v),f);}
template<class T>void rev(vector<T>&v){reverse(all(v));}
template<class T>void uni(vector<T>&v){sort(all(v));v.erase(unique(all(v)),end(v));}
void sort(string&s){sort(all(s));}
void rev(string&s){reverse(all(s));}
v1 iota(ll n,ll s=0){v1 a(n);iota(all(a),s);return a;}
void emplace_front(v1&v,ll x=0){v.emplace(begin(v),x);}


struct fast_ios{fast_ios(){cin.tie(nullptr);ios::sync_with_stdio(false);cout<<fixed<<setprecision(10);};}fast_ios_;
istream&operator>>(istream&is,mint&x){ll t;is>>t;x=t;return is;}
ostream&operator<<(ostream&os,const mint&x){return os<<x.val();}
template<class T,class U>istream&operator>>(istream&is,pair<T,U>&p){return is>>p.fst>>p.snd;}
template<class T,class U>ostream&operator<<(ostream&os,const pair<T,U>&p){return os<<p.fst<<" "<<p.snd;}
template<class T>istream&operator>>(istream&is,vector<T>&v){fore(x,v)is>>x;return is;}
template<class T>ostream&operator<<(ostream&os,const vector<T>&v){rep(i,sz(v))os<<v[i]<<(i==sz(v)-1?"":" ");return os;}
template<class T>ostream&operator<<(ostream&os,const vector<vector<T>>&v){rep(i,sz(v))os<<v[i]<<(i==sz(v)-1?"":"\n");return os;}
template<class T>ostream&operator<<(ostream&os,const set<T>&s){fore(x,s)os<<x<<(x==*rbegin(s)?"":" ");return os;}
template<class T,class U>ostream&operator<<(ostream&os,const map<T,U>&m){fore(k,v,m)os<<k<<" "<<v<<(k==(rbegin(m)->fst)?"":"\n");return os;}
template<class T>ostream&operator<<(ostream&os,const queue<T>&q){auto c=q;wh(sz(c))os<<c.front()<<" ",c.pop();return os;}
template<class T>ostream&operator<<(ostream&os,const deque<T>&q){auto c=q;wh(sz(c))os<<c.front()<<" ",c.pop_front();return os;}
template<class T>ostream&operator<<(ostream&os,const max_priority_queue<T>&q){auto c=q;wh(sz(c))os<<c.top()<<" ",c.pop();return os;}
template<class T>ostream&operator<<(ostream&os,const min_priority_queue<T>&q){auto c=q;wh(sz(c))os<<c.top()<<" ",c.pop();return os;}
ll pt(){cout<<'\n';return 0;}
ll db(){cerr<<'\n';return 0;}
template<class T,class...A>ll pt(const T&a,const A&...b){cout<<a;((cout<<' '<<b),...);return pt();}
template<class T,class...A>ll db(const T&a,const A&...b){cerr<<a;((cerr<<' '<<b),...);return db();}
template<class...T>void lin(T&...a){(cin>>...>>a);}
template<class...T>void vin(const ll&i,vector<T>&...a){(cin>>...>>a[i]);}
template<class T,class...A>void vin(vector<T>&a,A&...b){rep(i,sz(a))vin(i,a,b...);}
string first(bool f=1){return f?"first":"second";}
string First(bool f=1){return f?"First":"Second";}
string yes(bool f=1){return f?"yes":"no";}
string Yes(bool f=1){return f?"Yes":"No";}
string YES(bool f=1){return f?"YES":"NO";}
string no(){return "no";}
string No(){return "No";}
string NO(){return "NO";}
string possible(bool f=1){return f?"possible":"impossible";}
string Possible(bool f=1){return f?"Possible":"Impossible";}
string POSSIBLE(bool f=1){return f?"POSSIBLE":"IMPOSSIBLE";}


template<class V,class T>void resize(vector<V>&v,const T&a){v.resize(a);}
template<class V,class T,class...A>void resize(vector<V>&vv,const T&a,const A&...b){resize(vv,a);fore(v,vv)resize(v,b...);}
template<class V,class T>void fill(V&v,const T&x){v=x;}
template<class V,class T>void fill(vector<V>&vv,const T&x){fore(v,vv)fill(v,x);}
void zi(const v1&v,v1&h){fore(x,h)x=lbp(v,x);}
template<class...T>void zi(const v1&v,v1&h,T&...t){zi(v,h);zi(v,t...);}
template<class...T>v1 zip(T&...a){v1 v;fore(e,{a...})v+=e;uni(v);zi(v,a...);return v;}
template<class T>void vs(const v1&o,vector<T>&a){vector<T>c=a;rep(i,sz(a))a[i]=c[o[i]];}
template<class T,class...A>void vs(const v1&o,vector<T>&a,A&...b){vs(o,a);vs(o,b...);}
template<class F,class...T>pair<v1,v1>vsort(const F&f,T&...a){ll n=0;fore(e,{a...})n=sz(e);v1 o=iota(n),p(n);sort(o,f);rep(i,n)p[o[i]]=i;vs(o,a...);return{o,p};}
template<class T>T binsearch(const function<bool(T)>&j,T o,T n){T D=(*typeid(o).name()=='x'?1:eps);wh(abs(o-n)>D){T m=(o+n)/2;(j(m)?o:n)=m;}return o;}


v1 divisor(ll n){mll m;for(ll i=1;i*i<=n;i++){if(n%i==0){m[i]++;m[n/i]++;}}v1 v;fore(x,_,m)v.eb(x);return v;}
mll factor(ll n){mll m;for(ll i=2;i*i<=n;i++){wh(n%i==0){m[i]++;n/=i;}}if(n>1)m[n]++;return m;}
ll mpow(ll x,ll n,ll m=0){ll r=1;wh(n>0){if(n&1){r*=x;if(m)r%=m;}x*=x;if(m)x%=m;n>>=1;}return r;}
ll minv(ll a,ll m){ll b=m,u=1,v=0;wh(b){ll t=a/b;a-=t*b;swap(a,b);u-=t*v;swap(u,v);}u%=m;if(u<0)u+=m;return u;}
ll lsqrt(ll x){ll r=sqrtl(x)-1;wh(r+1<=x/(r+1))r++;return r;}
ll llog2(ll n){ll r=0;wh(n){n>>=1;r++;}return r;}
mint mhash(mint a){return a*(a+1346)*(a+9185);}
ll bit(ll n){return 1LL<<n;}
v1 dx={-1,0,1,0,-1,1,1,-1};
v1 dy={0,-1,0,1,-1,-1,1,1};
using S=ll;
S e(){return 0;}
S op(S a,S b){return a+b;}
using sgt=segtree<S,op,e>;


int main(){
  LL(N,K);
  v1 a(N);lin(a);
  ST(s);
  
  ll M=sz(zip(a));
  
  vector<vector<mint>>dp;resize(dp,K+1,N);
  rep(j,N)dp[0][j]=1;
  
  rep(i,1,K+1){
    fenwick_tree<mint>fw(M);
    rep(j,N){
      fw.add(a[j],dp[i-1][j]);
      dp[i][j]=(s[i-1]=='<'?fw.sum(0,a[j]):fw.sum(a[j]+1,M));
    }
  }
  pt(sum(dp[K]));
}

yukicoder

結果

テストケース

ソースコード