結果
問題 | No.1371 交換門松列・松 |
ユーザー |
|
提出日時 | 2021-01-29 22:40:28 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 101 ms / 4,000 ms |
コード長 | 1,407 bytes |
コンパイル時間 | 696 ms |
コンパイル使用メモリ | 82,016 KB |
実行使用メモリ | 7,296 KB |
最終ジャッジ日時 | 2024-06-27 09:01:31 |
合計ジャッジ時間 | 3,051 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
コンパイルメッセージ
a.cpp:10:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
ソースコード
#line 1 "a.cpp" #include<iostream> #include<vector> #include<algorithm> #include<queue> using namespace std; #line 1 "/home/kotatsugame/library/datastructure/BIT.cpp" //1-indexed #line 3 "/home/kotatsugame/library/datastructure/BIT.cpp" template<typename T> struct BIT{ int n; vector<T>bit; BIT(int n_=0):n(n_),bit(n_+1){} T sum(int i) { T ans=0; for(;i>0;i-=i&-i)ans+=bit[i]; return ans; } void add(int i,T a) { if(i==0)return; for(;i<=n;i+=i&-i)bit[i]+=a; } int lower_bound(T k)//k<=sum(ret) { if(k<=0)return 0; int ret=0,i=1; while((i<<1)<=n)i<<=1; for(;i;i>>=1) if(ret+i<=n&&bit[ret+i]<k)k-=bit[ret+=i]; return ret+1; } }; #line 7 "a.cpp" int N; int A[2<<17]; int id[2<<17]; main() { cin>>N; for(int i=0;i<N;i++) { cin>>A[i]; A[i]--; id[A[i]]=i; } vector<int>X; priority_queue<pair<int,int> >Y; long ans=0; BIT<int>P(N); for(int j=0;j<N;j++) { int i=id[j]; while(!Y.empty()&&-Y.top().first<=A[i]) { P.add(Y.top().second+1,-1); Y.pop(); } bool f=(i==0?A[i+1]:A[i-1])<A[i]; if(f) { int L=i==0?A[i+1]:A[i-1]; if(i+1<N&&L<A[i+1])L=A[i+1]; ans+=X.end()-upper_bound(X.begin(),X.end(),L); ans+=P.sum(N)-P.sum(L+1); X.push_back(A[i]); } else { int L=i==0?A[i+1]:A[i-1]; if(i+1<N&&L>A[i+1])L=A[i+1]; ans+=Y.size(); ans+=X.size(); P.add(A[i]+1,1); Y.push(make_pair(-L,A[i])); } } cout<<ans<<endl; }