QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #276816 | #7904. Rainbow Subarray | Redcrown# | WA | 243ms | 13004kb | C++17 | 2.6kb | 2023-12-06 11:07:15 | 2023-12-06 11:07:16 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define ssz(x) ((int)x.size())
using namespace std;
const int N=1e6+5;
ll n;
ll K,A[N];
inline int red(){
int data=0;bool w=0;char ch=getchar();
while(ch!='-' && (ch<'0' || ch>'9'))ch=getchar();
if(ch=='-') w=1,ch=getchar();
while(ch>='0' && ch<='9') data=(data<<3)+(data<<1)+ch-'0',ch=getchar();
return w?-data:data;
}
map <ll,ll> cnt;
set <ll> S;
ll calcNeed(ll sumx,ll x,ll sumz,ll z,ll midval){
return midval*x-sumx+sumz-midval*z;
}
void solve(){
scanf("%lld%lld",&n,&K);
cnt.clear();
S.clear();
for(int i=1;i<=n;i++){
scanf("%lld",&A[i]);
A[i]-=i;
}
int l=1,r=1,ans=1,flag=1;
ll sumx=0,x=0,y=1,yval=A[1],sumz=0,z=0;
cnt[A[1]]=1;
S.insert(A[1]);
// ll sumy=0;
while(flag){
flag=0;
while(r<n&&calcNeed(sumx,x,sumz,z,yval)<=K){
if(l<=r)ans=max(ans,r-l+1);
flag=1;
r++;
if(A[r]==yval){
// sumy+=A[r];
++y;
}else if(A[r]<yval){
sumx+=A[r];
x++;
}else{
sumz+=A[r];
z++;
}
S.insert(A[r]);
cnt[A[r]]+=1;
if(z>x+y){
sumx+=y*yval;
x+=y;
auto now=S.find(yval);
++now;
yval=*now;
y=cnt[yval];
sumz-=y*yval;
z-=y;
}
if(x>y+z){
sumz+=y*yval;
z+=y;
auto now=S.find(yval);
--now;
yval=*now;
y=cnt[yval];
sumx-=y*yval;
x-=y;
}
if(l<=r&&calcNeed(sumx,x,sumz,z,yval)<=K){
ans=max(ans,r-l+1);
}
}
while(calcNeed(sumx,x,sumz,z,yval)>K&&l<=r){
if(A[l]==yval){
// sumy-=yval;
--y;
}else if(A[l]<yval){
sumx-=A[l];
x--;
}else{
sumz-=A[l];
z--;
}
if(z>x+y){
sumx+=y*yval;
x+=y;
auto now=S.find(yval);
++now;
yval=*now;
y=cnt[yval];
sumz-=y*yval;
z-=y;
}
if(x>y+z){
sumz+=y*yval;
z+=y;
auto now=S.find(yval);
--now;
yval=*now;
y=cnt[yval];
sumx-=y*yval;
x-=y;
}
--cnt[A[l]];
if(cnt[A[l]]==0){
S.erase(A[l]);
}
flag=1;
l++;
}
}
printf("%d\n",ans);
}
int main()
{
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
int T=1;
T=red();
while(T--)solve();
return 0;
}
/*
1
7 2
50
7 5
7 2 5 5 4 11 7
6 0
100 3 4 5 99 100
5 6
1 1 1 1 1
5 50
100 200 300 400 500
1 100
3
7 2
2 3 3 4 5 6 7
7 1
2 3 3 4 5 6 7
7 0
2 3 3 4 5 6 7
8 4
1 4 3 3 3 3 2 5
7 2
1 3 4 6 8 10 12
7 5
1 3 4 6 8 10 12
7 7
1 3 4 6 8 10 12
8 2
12 1 3 4 6 8 10 12
4 3
3 3 6 8
4 4
3 3 6 8
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3796kb
input:
5 7 5 7 2 5 5 4 11 7 6 0 100 3 4 5 99 100 5 6 1 1 1 1 1 5 50 100 200 300 400 500 1 100 3
output:
4 3 5 1 1
result:
ok 5 lines
Test #2:
score: -100
Wrong Answer
time: 243ms
memory: 13004kb
input:
11102 2 167959139 336470888 134074578 5 642802746 273386884 79721198 396628655 3722503 471207868 6 202647942 268792718 46761498 443917727 16843338 125908043 191952768 2 717268783 150414369 193319712 6 519096230 356168102 262263554 174936674 407246545 274667941 279198849 9 527268921 421436316 3613460...
output:
1 4 3 2 6 5 7 2 4 1 4 1 1 2 2 2 7 8 7 7 1 7 6 2 4 3 1 6 7 7 3 4 3 9 3 8 6 6 3 1 6 3 1 2 4 6 2 6 4 1 4 7 1 6 3 5 6 6 1 7 5 3 1 6 4 5 3 2 2 6 2 3 10 1 4 3 2 4 5 1 7 5 5 5 8 5 3 6 3 5 5 8 5 4 5 2 1 5 2 4 3 4 8 1 3 1 2 2 8 3 1 6 8 1 8 4 5 6 6 8 4 8 3 2 8 4 5 6 2 6 2 4 1 5 4 5 3 2 4 1 2 1 3 5 8 3 7 3 3 2...
result:
wrong answer 14th lines differ - expected: '3', found: '2'