QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#543493 | #7685. Barkley II | AmiyaCast | TL | 4ms | 31172kb | C++14 | 1.6kb | 2024-09-01 16:59:36 | 2024-09-01 16:59:36 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int n,a[N],root[N],tot,m;
struct Node {
int l,r;
int cnt;
} tr[N*40];
int build(int l,int r) {
int p=++tot;
if(l==r) return p;
int mid=(l+r)>>1;
tr[p].l=build(l,mid),tr[p].r=build(mid+1,r);
return p;
}
int insert(int p,int idx,int l,int r,int x) {
int q=++tot;//点分裂
tr[q]=tr[p],tr[q].cnt+=x;
if(l<r) {
int mid=(l+r)>>1;
if(idx<=mid) tr[q].l=insert(tr[p].l,idx,l,mid,x);
else tr[q].r=insert(tr[p].r,idx,mid+1,r,x);
}
return q;
}
int query(int idx,int q,int l,int r) {
if(l==r) return tr[q].cnt;
int mid=(l+r)>>1;
if(idx<=mid) return query(idx,tr[q].l,l,mid)+tr[tr[q].r].cnt;
else return query(idx,tr[q].r,mid+1,r);
}
void solve() {
cin>>n>>m;
root[0]=build(1,n);
vector<int>g[N],last(m+1);
for(int i=1; i<=n; i++) {
cin>>a[i];
g[a[i]].push_back(i);
if(!last[a[i]]) // 该数据第一次出现
root[i]=insert(root[i-1],i,1,n,1);
else {
int t=insert(root[i-1],last[a[i]],1,n,-1);
root[i]=insert(t,i,1,n,1);
}
last[a[i]]=i;
}
int ans=0;
for(int i=1; i<=n; i++) {
g[i].push_back(0);
g[i].push_back(n+1);
sort(g[i].begin(),g[i].end());
for(int j=1; j<(int)g[i].size(); j++) {
int l=g[i][j-1]+1,r=g[i][j]-1;
ans=max(ans,query(l,root[r],1,n)-i);
}
}
cout<<ans<<'\n';
for(int i=0; i<=n; i++) root[i]=0;
for(int i=0; i<=tot; i++) {
tr[i]= {0,0,0};
}
tot=0;
}
signed main() {
int T;
cin>>T;
while(T--) solve();
return 0;
}
/*
1
5 4
1 2 2 3 4
*/
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 31172kb
input:
2 5 4 1 2 2 3 4 5 10000 5 2 3 4 1
output:
2 3
result:
ok 2 number(s): "2 3"
Test #2:
score: -100
Time Limit Exceeded
input:
50000 10 19 12 6 1 12 11 15 4 1 13 18 10 8 8 7 6 7 6 2 2 3 4 8 10 6 3 2 6 6 5 2 3 4 5 6 10 11 6 3 7 9 2 1 2 10 10 4 10 6 6 1 2 6 1 1 3 4 2 1 10 9 8 5 3 9 1 7 5 5 1 1 10 5 1 4 3 2 5 4 5 3 5 2 10 14 3 8 12 10 4 2 3 13 7 3 10 14 5 5 12 2 8 1 13 9 8 5 10 7 5 5 6 6 1 5 3 7 3 4 10 7 5 1 4 6 1 6 4 3 7 5 10...
output:
6 5 4 4 2 4 3 7 4 4 4 5 2 3 6 6 7 5 7 6 5 5 6 2 6 8 7 2 5 5 6 2 2 3 4 5 3 3 7 3 2 5 6 1 3 5 3 3 3 8 6 6 5 7 4 4 5 4 6 6 6 3 7 3 6 3 3 7 7 6 6 7 4 3 3 4 4 6 3 4 6 6 4 5 5 9 4 5 7 5 3 5 2 2 5 6 6 8 4 3 4 5 5 5 7 7 3 2 6 5 3 5 4 4 5 6 6 5 6 7 7 4 5 7 4 7 3 7 6 6 6 5 4 2 5 4 2 3 6 5 2 6 5 5 4 3 5 6 6 6 ...