Submission #63846500

---

Source Code Expand

// Problem: F - Variety Split Hard
// Contest: AtCoder - OMRON Corporation Programming Contest 2025 (AtCoder Beginner Contest 397)
// URL: https://atcoder.jp/contests/abc397/tasks/abc397_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//空中散歩の SOS 僕ファー　僕ファー　僕ファー ~
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef double db;
const ll maxn=3e5+5;
struct sgt{
	#define mid ((l+r)>>1)
	#define ls (x<<1)
	#define rs (x<<1|1)
	ll t[maxn<<2],g[maxn<<2];
	void upd(ll x){
		t[x]=max(t[ls],t[rs]);
	}
	void push_down(ll x,ll l,ll r){
		t[ls]+=g[x];
		t[rs]+=g[x];
		g[ls]+=g[x];
		g[rs]+=g[x];
		g[x]=0;
	}
	void clear(ll x,ll l,ll r){
		if(l==r){
			t[x]=0;
			g[x]=0;
			return ;
		}
		clear(ls,l,mid);
		clear(rs,mid+1,r);
		upd(x);
		return ;
	}
	void modify(ll x,ll l,ll r,ll L,ll R,ll val){
		if(L<=l&&r<=R){
			g[x]+=val;
			t[x]+=val;
			return ;
		}
		push_down(x,l,r);
		if(L<=mid)modify(ls,l,mid,L,R,val);
		if(R>mid)modify(rs,mid+1,r,L,R,val);
		upd(x);
		return ;
	}
	ll query(ll x,ll l,ll r,ll L,ll R){
		if(L<=l&&r<=R){
			return t[x];
		}
		push_down(x,l,r);
		ll res=0;
		if(L<=mid)res=max(res,query(ls,l,mid,L,R));
		if(R>mid)res=max(res,query(rs,mid+1,r,L,R));
		return res;
	}
}t;
vector<ll>lst[maxn];
ll a[maxn];
ll n,ans;
ll b[maxn];
void solve(){
	cin>>n;
	ll res=0;
	for(ll i=1;i<=n;i++){
		cin>>a[i];
		if(lst[a[i]].empty())res++;
		lst[a[i]].push_back(i);
	}
	for(ll i=1;i<=n;i++){
		if(lst[i].size()>1){
			t.modify(1,1,n,*lst[i].begin(),lst[i].back()-1,1);
		}
	}
	ans=res;
	// cerr<<n+1<<" "<<res<<endl;
	for(ll i=n;i>1;i--){
		if(!b[a[i]])res++;
		b[a[i]]++;
		if(lst[a[i]].size()<=0){
			ans=max(ans,res+t.query(1,1,n,1,i-1));
			// cerr<<i<<" "<<res+t.query(1,1,n,1,i-1)<<endl;
			continue;
		}
		else if(lst[a[i]].size()==1){
			res--;
			ans=max(ans,res+t.query(1,1,n,1,i-1));
			// cerr<<i<<" "<<res<<" "<<t.query(1,1,n,1,i-1)<<endl;
			continue;
		}
		ll it=lst[a[i]].back()-1;
		lst[a[i]].pop_back();
		t.modify(1,1,n,lst[a[i]].back(),it,-1);
		ans=max(ans,res+t.query(1,1,n,1,i-1));
		// cerr<<i<<" "<<res<<" "<<t.query(1,1,n,1,i-1)<<endl;
	}
	cout<<ans<<endl;
	return ;
}
ll T=1;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
//	cin>>T;
	for(ll kase=1;kase<=T;kase++){
		solve();
	}
	return 0;
}

Submission Info

Compile Error

Main.cpp: In member function ‘void sgt::push_down(ll, ll, ll)’:
Main.cpp:24:32: warning: unused parameter ‘l’ [-Wunused-parameter]
   24 |         void push_down(ll x,ll l,ll r){
      |                             ~~~^
Main.cpp:24:37: warning: unused parameter ‘r’ [-Wunused-parameter]
   24 |         void push_down(ll x,ll l,ll r){
      |                                  ~~~^

Judge Result