| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1198239 | nouka28 | 서열 (APIO23_sequence) | C++20 | 0 ms | 0 KiB |
#include "sequence.h"
#include<bits/stdc++.h>
using namespace std;
#include<atcoder/all>
using namespace atcoder;
using mint=atcoder::modint998244353;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
// #define int long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define rng(i,l,r) for(int i=(l);i<(r);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrng(i,l,r) for(int i=(r)-1;i>=(l);i--)
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
struct dat{
int l=0,r=0,sml=0,smr=0;
};
using S=pair<dat,dat>;
S op(S a,S b){
S ret;
ret.fi.l=min(a.fi.l+b.fi.sml,b.fi.l);
ret.fi.r=max(a.fi.r+b.fi.smr,b.fi.r);
ret.fi.sml=a.fi.sml+b.fi.sml;
ret.fi.smr=a.fi.smr+b.fi.smr;
ret.se.l=min(a.se.l,b.se.l+a.se.sml);
ret.se.r=max(a.se.r,b.se.r+a.se.smr);
ret.se.sml=a.se.sml+b.se.sml;
ret.se.smr=a.se.smr+b.se.smr;
return ret;
}
S e(){
return S();
}
int sequence(int N, std::vector<int> A) {
// cout<<"N : "<<N<<endl;
// cout<<"A : ";for(auto&&e:A)cout<<e<<" ";cout<<endl;
for(auto&&e:A)e--;
vector<vector<int>> g(N);
rep(i,N)g[A[i]].push_back(i);
int ans=0;
segtree<S,op,e> seg;
{
S t={{1,1,1,1},{1,1,1,1}};
seg=segtree<S,op,e>(vector<S>(N,t));
}
rep(i,N){
if(!g[i].size())continue;
// cout<<"i : "<<i<<endl;
vector<int> vs=g[i];
for(auto&&p:vs){
seg.set(p,{{-1,1,-1,1},{-1,1,-1,1}});
}
// cout<<"seg : ";rep(j,N)cout<<seg.get(j).fi.l<<" ";cout<<endl;
// cout<<i<<" : ";
// for(auto&&e:vs)cout<<e<<" ";cout<<endl;
rep(j,vs.size()){
seg.set(vs[j],{{-1,-1,-1,-1},{-1,-1,-1,-1}});
int ok=j,ng=vs.size();
while(abs(ok-ng)>1){
// cout<<"!"<<j<<" "<<ok<<" "<<ng<<endl;
int mid=(ok+ng)>>1;
auto t1=seg.prod(0,vs[j]);
auto t2=seg.prod(vs[j],vs[mid]+1);
auto t3=seg.prod(vs[mid]+1,N);
int l=t1.fi.l+t3.se.l;
int r=t1.fi.r+t3.se.r;
l+=t2.fi.sml,r+=t2.fi.smr+1;
// cout<<j<<" "<<ok<<" : "<<l<<" "<<r<<endl;
// cout<<"! "<<t1.fi.l<<" "<<t1.fi.r<<" , "<<t2.fi.l<<" "<<t2.fi.r<<endl;
if(r<=-1||1<=l){
ng=mid;
}else{
ok=mid;
}
}
seg.set(vs[j],{{-1,1,-1,1},{-1,1,-1,1}});
ans=max(ans,ok-j+1);
}
for(auto&&p:vs){
seg.set(p,{{-1,-1,-1,-1},{-1,-1,-1,-1}});
}
}
// cout<<"ans : "<<ans<<endl;
return ans;
}