QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#543493#7685. Barkley IIAmiyaCastTL 4ms31172kbC++141.6kb2024-09-01 16:59:362024-09-01 16:59:36

Judging History

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

  • [2024-09-01 16:59:36]
  • 评测
  • 测评结果:TL
  • 用时:4ms
  • 内存:31172kb
  • [2024-09-01 16:59:36]
  • 提交

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
...

result: