結果
問題 | No.2374 ASKT Subsequences |
ユーザー |
![]() |
提出日時 | 2023-07-08 01:13:10 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 97 ms / 2,000 ms |
コード長 | 1,747 bytes |
コンパイル時間 | 1,134 ms |
コンパイル使用メモリ | 115,976 KB |
実行使用メモリ | 38,616 KB |
最終ジャッジ日時 | 2024-07-21 21:32:01 |
合計ジャッジ時間 | 2,584 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include<iostream>#include<vector>#include<string>#include<algorithm>#include<set>#include<queue>using namespace std;using ll = long long;template< typename T >struct BIT2D{int H,W;vector<vector<T>> data;BIT2D(int h,int w):H(h),W(w),data(h+1,vector<T>(w+1,0)){}void add(int h,int w,T x){h++;w++;for(int i = h;i<=H;i+=i&(-i)){for(int j = w;j<=W;j+=j&(-j)){data[i][j] += x;}}}//sum of [l,r)T sum(int h1,int w1,int h2,int w2){return sum(h2,w2)-sum(h2,w1-1)-sum(h1-1,w2)+sum(h1-1,w1-1);}T sum(int h,int w){h++;w++;T now = 0;for(int i = h;i>0;i-=i&(-i)){for(int j = w;j>0;j-=j&(-j)){now += data[i][j];}}return now;}};int main(){int n;cin>>n;vector<int> a(n);for(int i = 0;i<n;i++) cin>>a[i];ll ans = 0;vector<vector<pair<int,int>>> u1(2001),u2(2001);for(int i = 0;i<n;i++) for(int j = i+1;j<n;j++){if(a[j]==a[i]+10) {u1[a[i]].push_back(make_pair(i,j));}if(a[j]==a[i]+1){u2[a[i]].push_back(make_pair(i,j));}}BIT2D<ll> b(n+1,n+1);for(int i = 2000;i>=0;i--){int want = i + 11;if(want<=2000){for(int j = 0;j<u2[want].size();j++){int ni = u2[want][j].first;int nj = u2[want][j].second;b.add(ni,nj,1);}}for(int j = 0;j<u1[i].size();j++){int ni = u1[i][j].first;int nj = u1[i][j].second;ans += b.sum(ni+1,nj+1,nj,n);}}cout <<ans<<endl;}