QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#49940#4836. TreeCrysflyRE 0ms0kbC++112.7kb2022-09-24 08:24:382022-09-24 08:25:31

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-24 08:25:31]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2022-09-24 08:24:38]
  • 提交

answer

#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 200005
#define inf 0x3f3f3f3f

int n,m,a[maxn],res[maxn];
map<int,int>mp; int tov[maxn];
inline int ID(int x){
	if(!mp.count(x))return tov[++m]=x,mp[x]=m;
	return mp[x];
}

vi p[maxn];
int pos[maxn][405];
int sum[maxn],lst[maxn],mx[maxn],mn[maxn];

void big(int x)
{
	For(i,1,n)mx[i]=1,mn[i]=lst[i]=0,sum[i]=sum[i-1]+(a[i]==x);
	For(i,1,n)
		if(a[i]!=x){
			int u=a[i];
			if(lst[u])mx[u]=max(mx[u]+1-(sum[i]-sum[lst[u]]),0);
			else mx[u]=1;
			mn[u]-=(sum[i]-sum[lst[u]]);
			res[x]=max(res[x],(int)p[x].size()+mx[u]);
			res[u]=max(res[u],(int)p[u].size()-mn[u]);
			mn[u]=min(mn[u]+1,0);
			lst[u]=i;
		}
}

int tmp[maxn];
int cal(int l,int r){
	int res=0;
	For(i,l,r)res=max(res,++tmp[a[i]]);
	For(i,l,r)--tmp[a[i]];
	return res;
}

void small(int x)
{
//	cout<<"Small "<<x<<endl;
	int sz=p[x].size();
	For(i,-1,sz-1){
		int c=1,pi=(i==-1?0:p[x][i]);
		For(j,i+1,sz){
			int pj=(j==sz?n+1:p[x][j]);
			if(pi+1==pj)continue; 
			while(c+1<=400 && pos[pi+1][c+1]<=pj-1) ++c;
			res[x]=max(res[x],sz-(j-i-1)+c);
		}
	}
}

int out[maxn],len;
void work()
{
	n=read(),m=0,mp.clear();
	For(i,1,n)p[i].clear(),res[i]=0;
	For(i,1,n){
		pos[i][1]=i;
		For(j,2,400)pos[i][j]=n+2;
	} 
	For(i,1,n)a[i]=read(),a[i]=ID(a[i]),p[a[i]].pb(i);
//	For(i,1,n)cout<<a[i]<<' ';puts("");
	For(i,1,m)res[i]=p[i].size();
	For(i,1,m)
		if(p[i].size()<=400){
			int sz=p[i].size();
	//		cout<<"sz "<<i<<' '<<p[i].size()<<endl;
			For(x,0,sz-1)
				For(y,x+1,sz-1)
					pos[p[i][x]][y-x+1]=min(pos[p[i][x]][y-x+1],p[i][y]);//cout<<"addx "<<p[i][x]<<' '<<y-x+1<<' '<<p[i][y]<<endl;
		}
	Rep(i,n-1,1){
		For(j,2,400)
			pos[i][j]=min(pos[i][j],pos[i+1][j]);
		For(j,2,399)
			pos[i][j]=min(pos[i][j],pos[i][j+1]);
	}
//	For(i,1,n)For(j,1,5)cout<<pos[i][j]<<" \n"[j==5];
	For(i,1,m)
		if(p[i].size()<=400)small(i);
		else big(i);
	len=0;
	int mx=0;
	For(i,1,m)mx=max(mx,res[i]);
//	For(i,1,m)cout<<"val: "<<tov[i]<<" "<<res[i]<<endl;
	printf("%d\n",mx);
	For(i,1,m)if(res[i]==mx)out[++len]=tov[i];
	sort(out+1,out+len+1);
	For(i,1,len)printf("%d\n",out[i]);
}

signed main()
{
//	freopen("mode9.in","r",stdin);
//	freopen("my.out","w",stdout);
	int T=read();
	while(T--)work();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

5 998244353

output:


result: