QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#311340 | #7904. Rainbow Subarray | confesser | TL | 1ms | 9716kb | C++17 | 1.6kb | 2024-01-22 11:04:33 | 2024-01-22 11:04:34 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using pi=pair<int,int>;
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define G(i,a,b) for(int i=(a);i>=(b);i--)
#define ms(a,b) memset(a,b,sizeof(a))
#define si(a) ((int)(a).size())
#define all(a) (a).begin(),(a).end()
#define fi first
#define se second
#define pb push_back
const int N=5e5+3;
int n,a[N],b[N],m,rk[N];
struct bit{
int n;
ll c[N];
void init(int m){
n=m;
F(i,1,n) c[i]=0;
}
void add(int i,ll k){
for(;i<=n;i+=i&-i) c[i]+=k;
}
ll qry(int i){
int res=0;
for(;i>=1;i-=i&-i) res+=c[i];
return res;
}
ll qry(int l,int r){
if(l>r) return 0;
return qry(r)-qry(l-1);
}
}c1,c2;
void add(int x){
c1.add(rk[x],1);
c2.add(rk[x],a[x]);
}
void del(int x){
c1.add(rk[x],-1);
c2.add(rk[x],-a[x]);
}
int get(){
int n=c1.qry(m),l=1,r=m,res=0;
while(l<=r){
int mid=(l+r)>>1;
if(c1.qry(mid-1)<=n/2){
res=mid;
l=mid+1;
}else r=mid-1;
}
return b[res];
}
ll val(){
int x=get(),y=upper_bound(b+1,b+m+1,x)-b-1;
return (ll)c1.qry(y)*x-c2.qry(y)+c2.qry(y+1,m)-(ll)c1.qry(y+1,m)*x;
}
void slv(){
ll k;
cin>>n>>k;
F(i,1,n){
cin>>a[i];
a[i]-=i;
b[++m]=a[i];
}
sort(b+1,b+m+1);
m=unique(b+1,b+m+1)-b-1;
F(i,1,n) rk[i]=lower_bound(b+1,b+m+1,a[i])-b;
c1.init(m);
c2.init(m);
int j=1,ans=0;
F(i,1,n){
add(i);
while(j<i&&val()>k) del(j++);
ans=max(ans,i-j+1);
}
cout<<ans<<'\n';
}
int main(){
cin.tie(0)->ios::sync_with_stdio(0);
int t;
cin>>t;
while(t--) slv();
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 9716kb
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
Time Limit Exceeded
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 3 2 2 7 9 7 10 1 7 6 2 4 3 1 7 7 7 3 4 3 10 3 8 6 6 3 1 6 3 1 2 4 6 4 7 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 9 5 4 5 2 1 5 2 3 3 4 8 1 3 1 2 2 8 3 1 6 8 1 8 4 5 6 6 10 4 8 3 2 8 4 5 6 2 6 2 4 1 5 4 5 3 2 4 1 2 1 4 5 8 3 7 3 ...