なんか順調で1位が取れた回。
https://codeforces.com/contest/1454/problem/F
問題
整数列Aが与えられる。
Aを空でない連続部分列B+C+Dに分割したとき、max(B)=min(C)=max(D)となるようにできるか。
解法
max(B)=min(C)=max(D)=mとしてmを総当たりする。
m未満の値の添え字の集合Lと、mを超えた値の添え字の集合Rを考える。
Aのうちm未満の値はBまたはD、mより大きな値はCに入るようにできるかL,Rを使って判定すればよい。
int T; int N; ll A[202020]; set<int> L,R; map<int,set<int>> M; void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>N; L.clear(); R.clear(); M.clear(); L.insert(-1); L.insert(N+1); FOR(i,N) { cin>>A[i]; M[-A[i]].insert(i); L.insert(i); } vector<int> ret; FORR(m,M) { x=m.first; auto v=m.second; FORR(c,v) L.erase(c); if(v.size()>=3) { if(R.empty()) { x=*next(v.begin()); ret={x,1,N-(x+1)}; } else { int a=-1,b=-1; if(R.size()==1) { a=b=*R.begin(); } else if(R.size()>=2) { a=*R.begin(); b=*R.rbegin(); if(*L.lower_bound(a)<b) { a=N+1; } } if(a<=N) { int lR=min(*v.rbegin(),*L.lower_bound(b)); int lL=max(*v.begin(),*prev(L.lower_bound(a))); int lM=*v.lower_bound(lL+1); if(lM<lR&&lR>*R.rbegin()&&lL<*R.begin()) { //cout<<x<<" "<<a<<" "<<b<<" "<<lL<<" "<<lM<<" "<<lR<<endl; ret={lL+1,lR-(lL+1),N-lR}; } } } } FORR(c,v) R.insert(c); } if(ret.size()) { cout<<"YES"<<endl; cout<<ret[0]<<" "<<ret[1]<<" "<<ret[2]<<endl; } else { cout<<"NO"<<endl; } } }
まとめ
結構時間かかったけどなんかいい順位だった。前半が良かったのかな。