QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#258224 | #7685. Barkley II | daydream# | WA | 76ms | 3508kb | C++20 | 1.5kb | 2023-11-19 16:08:35 | 2023-11-19 16:08:36 |
Judging History
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'