QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#49940 | #4836. Tree | Crysfly | RE | 0ms | 0kb | C++11 | 2.7kb | 2022-09-24 08:24:38 | 2022-09-24 08:25:31 |
Judging History
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;
}
詳細信息
Test #1:
score: 0
Runtime Error
input:
5 998244353