結果
問題 | No.1975 Zigzag Sequence |
ユーザー | eQe |
提出日時 | 2022-06-11 11:18:17 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 91 ms / 2,000 ms |
コード長 | 5,174 bytes |
コンパイル時間 | 4,462 ms |
コンパイル使用メモリ | 280,740 KB |
実行使用メモリ | 7,288 KB |
最終ジャッジ日時 | 2024-09-21 20:10:51 |
合計ジャッジ時間 | 7,368 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
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 | 10 ms
5,376 KB |
testcase_04 | AC | 5 ms
5,376 KB |
testcase_05 | AC | 76 ms
5,376 KB |
testcase_06 | AC | 50 ms
5,376 KB |
testcase_07 | AC | 11 ms
5,376 KB |
testcase_08 | AC | 53 ms
5,376 KB |
testcase_09 | AC | 79 ms
5,616 KB |
testcase_10 | AC | 55 ms
5,376 KB |
testcase_11 | AC | 61 ms
5,376 KB |
testcase_12 | AC | 16 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 2 ms
5,376 KB |
testcase_18 | AC | 31 ms
5,376 KB |
testcase_19 | AC | 31 ms
5,376 KB |
testcase_20 | AC | 51 ms
5,376 KB |
testcase_21 | AC | 52 ms
5,376 KB |
testcase_22 | AC | 77 ms
7,280 KB |
testcase_23 | AC | 75 ms
7,280 KB |
testcase_24 | AC | 78 ms
7,156 KB |
testcase_25 | AC | 78 ms
7,284 KB |
testcase_26 | AC | 77 ms
5,376 KB |
testcase_27 | AC | 91 ms
6,004 KB |
testcase_28 | AC | 77 ms
7,288 KB |
testcase_29 | AC | 76 ms
7,288 KB |
testcase_30 | AC | 79 ms
7,280 KB |
testcase_31 | AC | 77 ms
7,284 KB |
testcase_32 | AC | 32 ms
5,376 KB |
testcase_33 | AC | 31 ms
5,376 KB |
testcase_34 | AC | 80 ms
5,376 KB |
testcase_35 | AC | 87 ms
5,376 KB |
ソースコード
#include<atcoder/all> #include<bits/stdc++.h> using namespace atcoder; using namespace std; #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define fin(a) return pt(a) #define rep(i,n) for(ll i=0;i<(ll)(n);i++) 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 mll=map<ll,ll>; ll inf=3e18; ld pi=acos(-1); ld eps=1e-10; 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>bool chmax(T&a,const T&b){return a<b?a=b,1:0;} template<class T>bool chmin(T&a,const T&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>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)-a.begin();} template<class T>ll ubp(const vector<T>&a,const T&b){return upper_bound(all(a),b)-a.begin();} template<class T>pll mima(const T&a,const T&b){return {min(a,b),max(a,b)};} 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 usort(vector<T>&v){sort(all(v));v.erase(unique(all(v)),v.end());} ostream&operator<<(ostream&os,const modint1000000007&x){return os<<x.val();} ostream&operator<<(ostream&os,const modint998244353&x){return os<<x.val();} ostream&operator<<(ostream&os,const modint&x){return os<<x.val();} template<class T1,class T2>istream&operator>>(istream&is,pair<T1,T2>&p){return is>>p.first>>p.second;} template<class T1,class T2>ostream&operator<<(ostream&os,const pair<T1,T2>&p){return os<<p.first<<" "<<p.second;} template<class T>istream&operator>>(istream&is,vector<T>&v){for(T&x:v)is>>x;return is;} template<class T>ostream&operator<<(ostream&os,const vector<T>&v){rep(i,v.size())os<<v[i]<<(i+1==(ll)v.size()?"":" ");return os;} template<class...A>ll pt_rest(){cout<<'\n';return 0;} template<class...A>ll pt(){cout<<'\n';return 0;} template<class T,class...A>ll pt_rest(const T&first,const A&...rest){cout<<" "<<first;pt_rest(rest...);return 0;} template<class T,class...A>ll pt(const T&first,const A&...rest){cout<<first;pt_rest(rest...);return 0;} template<class V,class H>void resize(vector<V>&vec,const H head){vec.resize(head);} template<class V,class H,class...T>void resize(vector<V>&vec,const H&head,const T...tail){vec.resize(head);for(auto&v:vec)resize(v,tail...);} template<class V,class T>void fill(V&x,const T&val){x=val;} template<class V,class T>void fill(vector<V>&vec,const T&val){for(auto&v:vec)fill(v,val);} template<class H>void vin(istream&is,const ll idx,vector<H>&head){is>>head[idx];} template<class H,class...T>void vin(istream&is,const ll idx,vector<H>&head,T&...tail){vin(is>>head[idx],idx,tail...);} template<class H,class...T>void vin(istream&is,vector<H>&head,T&...tail){rep(i,head.size())vin(is,i,head,tail...);} template<class H,class...T>void vin(vector<H>&head,T&...tail){vin(cin,head,tail...);} template<class H>void sin(istream&is,H&head){is>>head;} template<class H,class...T>void sin(istream&is,H&head,T&...tail){sin(is>>head,tail...);} template<class H,class...T>void sin(H&head,T&...tail){sin(cin,head,tail...);} template<class T>void printv2(vector<vector<T>>&a){rep(i,a.size()){rep(j,a[0].size())cout<<a[i][j]<<" ";pt();}} 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;for(auto[x,_]:m)v.emplace_back(x);return v;} mll factor(ll n){mll m;for(ll i=2;i*i<=n;i++){while(n%i==0){m[i]++;n/=i;}}if(n>1)m[n]++;return m;} ll lpow(ll x,ll n,ll m=0){ll r=1;while(n>0){if(n&1){r*=x;if(m)r%=m;}x*=x;if(m)x%=m;n>>=1;}return r;} ll lsqrt(ll x){assert(x>=0);if(x<=1)return x;ll r=sqrt(x)-1;while(r+1<=x/(r+1))r++;return r;} ll llog2(ll n){ll r=0;while(n){n>>=1;r++;}return r;} ll bit(ll n){return 1LL<<n;} v1 dx={0,-1,0,1},dy={-1,0,1,0}; using mint=modint1000000007; using S=mint; S op(S a,S b){return a+b;} S e(){return 0;} void com1(v1&v,v1&h){for(ll x:h)v.emplace_back(x);} template<class...T>void com1(v1&v,v1&h,T&...t){for(ll x:h)v.emplace_back(x);com1(v,t...);} void com2(v1&v,v1&h){rep(i,h.size())h[i]=lbp(v,h[i]);} template<class...T>void com2(v1&v,v1&h,T&...t){rep(i,h.size())h[i]=lbp(v,h[i]);com2(v,t...);} template<class...A>v1 compress(A&...a){v1 v;com1(v,a...);usort(v);com2(v,a...);return v;} int main(void){ cin.tie(nullptr); ios::sync_with_stdio(false); ll N;cin>>N; v1 a(N);cin>>a; ll M=compress(a).size(); segtree<S,op,e>seg(M); vector<mint>low(N,1),high(N,1); rep(i,N){ low[i]*=seg.prod(0,a[i]); high[i]*=seg.prod(a[i]+1,M); seg.set(a[i],seg.get(a[i])+mint(2).pow(i)); } seg=segtree<S,op,e>(M); for(ll i=N-1;i>=0;i--){ low[i]*=seg.prod(0,a[i]); high[i]*=seg.prod(a[i]+1,M); seg.set(a[i],seg.get(a[i])+mint(2).pow(N-i-1)); } pt(sum(low)+sum(high)); }