結果
問題 | No.1079 まお |
ユーザー | beet |
提出日時 | 2020-06-12 22:12:03 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 899 ms / 2,000 ms |
コード長 | 3,920 bytes |
コンパイル時間 | 2,866 ms |
コンパイル使用メモリ | 232,460 KB |
実行使用メモリ | 28,448 KB |
最終ジャッジ日時 | 2023-09-06 10:31:58 |
合計ジャッジ時間 | 12,005 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 1 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 2 ms
4,376 KB |
testcase_06 | AC | 3 ms
4,380 KB |
testcase_07 | AC | 5 ms
4,376 KB |
testcase_08 | AC | 5 ms
4,380 KB |
testcase_09 | AC | 5 ms
4,376 KB |
testcase_10 | AC | 5 ms
4,376 KB |
testcase_11 | AC | 5 ms
4,376 KB |
testcase_12 | AC | 212 ms
15,384 KB |
testcase_13 | AC | 128 ms
17,616 KB |
testcase_14 | AC | 391 ms
20,928 KB |
testcase_15 | AC | 284 ms
23,080 KB |
testcase_16 | AC | 224 ms
25,300 KB |
testcase_17 | AC | 595 ms
20,852 KB |
testcase_18 | AC | 200 ms
20,556 KB |
testcase_19 | AC | 899 ms
20,668 KB |
testcase_20 | AC | 621 ms
20,780 KB |
testcase_21 | AC | 450 ms
20,880 KB |
testcase_22 | AC | 413 ms
28,148 KB |
testcase_23 | AC | 382 ms
28,244 KB |
testcase_24 | AC | 472 ms
28,232 KB |
testcase_25 | AC | 577 ms
28,248 KB |
testcase_26 | AC | 612 ms
28,284 KB |
testcase_27 | AC | 90 ms
8,740 KB |
testcase_28 | AC | 208 ms
17,760 KB |
testcase_29 | AC | 286 ms
28,448 KB |
testcase_30 | AC | 302 ms
28,172 KB |
testcase_31 | AC | 97 ms
8,256 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} using Int = long long; const char newl = '\n'; template <typename T> struct SegmentTree{ using F = function<T(T,T)>; int n; F f; T ti; vector<T> dat; SegmentTree(){} SegmentTree(F f,T ti):f(f),ti(ti){} void init(int n_){ n=1; while(n<n_) n<<=1; dat.assign(n<<1,ti); } void build(const vector<T> &v){ int n_=v.size(); init(n_); for(int i=0;i<n_;i++) dat[n+i]=v[i]; for(int i=n-1;i;i--) dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]); } void set_val(int k,T x){ dat[k+=n]=x; while(k>>=1) dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]); } T query(int a,int b){ if(a>=b) return ti; T vl=ti,vr=ti; for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1) { if(l&1) vl=f(vl,dat[l++]); if(r&1) vr=f(dat[--r],vr); } return f(vl,vr); } template<typename C> int find(int st,C &check,T &acc,int k,int l,int r){ if(l+1==r){ acc=f(acc,dat[k]); return check(acc)?k-n:-1; } int m=(l+r)>>1; if(m<=st) return find(st,check,acc,(k<<1)|1,m,r); if(st<=l&&!check(f(acc,dat[k]))){ acc=f(acc,dat[k]); return -1; } int vl=find(st,check,acc,(k<<1)|0,l,m); if(~vl) return vl; return find(st,check,acc,(k<<1)|1,m,r); } template<typename C> int find(int st,C &check){ T acc=ti; return find(st,check,acc,1,0,n); } }; //INSERT ABOVE HERE signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n,k; cin>>n>>k; vector<int> as(n); for(int i=0;i<n;i++) cin>>as[i]; using P = pair<int, int>; vector<P> vp; for(int i=0;i<n;i++) vp.emplace_back(as[i],i); auto f=[&](P a,P b){return min(a,b);}; P ti(2e9,-1); SegmentTree<P> seg(f,ti); seg.build(vp); queue<P> que; que.emplace(0,n); map<int, vector<int>> G; for(int i=0;i<n;i++) G[as[i]].emplace_back(i); for(auto& [key, vs]:G) vs.emplace_back(n); // [c, d) auto cnt=[&](int key,int c,int d)->int{ if(!G.count(key)) return 0; auto &vs=G[key]; int l=lower_bound(vs.begin(),vs.end(),c)-vs.begin(); int r=lower_bound(vs.begin(),vs.end(),d)-vs.begin(); return r-l; }; using ll = long long; map<int, vector<ll>> S; for(auto& [key, vs]:G){ auto &sm=S[key]; sm.resize(vs.size()+1,0); for(int i=0;i<(int)vs.size();i++) sm[i+1]=sm[i]+vs[i]; }; // [c, d) auto sum=[&](int key,int c,int d)->ll{ if(!G.count(key)) return 0; auto &vs=G[key]; int l=lower_bound(vs.begin(),vs.end(),c)-vs.begin(); int r=lower_bound(vs.begin(),vs.end(),d)-vs.begin(); return S[key][r]-S[key][l]; }; ll ans=0; while(!que.empty()){ vector<int> idxs; { auto [l,r]=que.front();que.pop(); if(r-l<1) continue; int val=seg.query(l,r).first; idxs.emplace_back(l-1); while(seg.query(l,r).first==val){ int i=seg.query(l,r).second; idxs.emplace_back(i); seg.set_val(i,ti); } idxs.emplace_back(r); } for(int i=0;i+2<(int)idxs.size();i++){ int a=idxs[i+0]+1,b=idxs[i+1]; int c=idxs[i+1]+1,d=idxs[i+2]; // cerr<<a<<' '<<b<<':'<<c<<' '<<d<<endl; if(b-a<d-c){ for(int i=a;i<b;i++){ ans+=cnt(k-as[i],c,d)*ll(1-i); ans+=sum(k-as[i],c,d); } }else{ for(int i=c;i<d;i++){ ans+=cnt(k-as[i],a,b)*ll(i+1); ans-=sum(k-as[i],a,b); } } int p=idxs[i+1]; if(as[p]*2==k) ans+=1; ans+=cnt(k-as[p],c,d)*ll(1-p); ans+=sum(k-as[p],c,d); ans+=cnt(k-as[p],a,b)*ll(p+1); ans-=sum(k-as[p],a,b); } for(int i=0;i+1<(int)idxs.size();i++){ int a=idxs[i]+1,b=idxs[i+1]; que.emplace(a,b); } } cout<<ans<<newl; return 0; }