QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#258224#7685. Barkley IIdaydream#WA 76ms3508kbC++201.5kb2023-11-19 16:08:352023-11-19 16:08:36

Judging History

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

  • [2023-11-19 16:08:36]
  • 评测
  • 测评结果:WA
  • 用时:76ms
  • 内存:3508kb
  • [2023-11-19 16:08:35]
  • 提交

answer

#include<bits/stdc++.h>
#define LL long long
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int infi=1e9,mod=998244353;
void upd(int &x,const int y) {if((x+=y)>=mod) x-=mod;}

struct BIT
{
	int n;
	vector<int> tr;
	BIT(int N)
	{
		n=N;
		tr.resize(n+10);
	}
	void upd(int i,int v) {for(;i<=n;i+=(i&-i)) tr[i]+=v;}
	int qry(int i) {int res=0; for(;i;i-=(i&-i)) res+=tr[i]; return res;}
	int qry(int l,int r) {if(l>r) return 0; return qry(r)-qry(l-1);}
};
int n,m;
void solve()
{
	cin>>n>>m;vector<vector<int>> ps(n+1);
	vector<int> a(n+1,0),lst(n+1,0);
	for(int i=1;i<=n;++i)
	{
		cin>>a[i];
		if(a[i]<=n) ps[a[i]].eb(i);
	}
	vector<array<int,3>> qry;
	for(int i=1;i<=n;++i)
	{
		int l=0;
		for(auto r:ps[i])
		{
			if(l+1<r) qry.pb({r-1,l+1,i});
			lst[r]=l;l=r;
		}
		qry.pb({n,l+1,i});
	}
	BIT T(n);sort(qry.begin(),qry.end());
	int ans=-1,sz=qry.size();
//	for(int i=0;i<sz;++i) cout<<qry[i][0]<<' '<<qry[i][1]<<' '<<qry[i][2]<<'\n';
//	cout<<sz<<'\n';
	for(int i=1,j=0;i<=n;++i)
	{
		if(lst[i]) T.upd(lst[i],-1);
		T.upd(i,1);
		for(;j<sz&&qry[j][0]==i;++j)
		{
//			cout<<qry[j][1]<<' '<<i<<' '<<qry[j][2]<<'\n';
			ans=max(ans,T.qry(qry[j][1],i)-qry[j][2]);
//			cout<<ans<<'\n';
		}
	}
	cout<<ans<<'\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int TT=1;
	cin>>TT;
	for(;TT;--TT) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3380kb

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
Wrong Answer
time: 76ms
memory: 3508kb

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:

7
5
4
4
2
4
3
7
4
4
4
5
2
3
9
6
7
6
7
6
5
8
7
2
6
9
7
2
6
5
6
2
2
3
4
5
4
3
7
3
2
6
6
1
3
6
3
3
3
8
8
6
5
7
4
4
5
5
7
6
8
3
8
3
6
3
3
7
7
8
7
7
4
3
3
4
8
7
3
4
6
6
4
5
8
9
4
5
7
5
3
5
2
2
5
6
7
8
4
3
4
7
7
6
7
7
3
2
6
5
3
5
6
4
6
6
6
6
8
7
7
5
5
8
4
8
5
8
6
7
6
5
6
2
5
4
2
3
6
6
2
6
5
5
4
3
5
6
6
9
...

result:

wrong answer 1st numbers differ - expected: '6', found: '7'