QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#321295 | #7904. Rainbow Subarray | haze | WA | 123ms | 6364kb | C++23 | 2.4kb | 2024-02-04 13:10:05 | 2024-02-04 13:10:07 |
Judging History
answer
/*
Rainbow Subarray
https://codeforces.com/gym/104901/problem/K
Author: haze
*/
#include <bits/stdc++.h>
#define irep(i, l, r) for(int i = (l); i <= (r); ++ i)
#define drep(i, r, l) for(int i = (r); i >= (l); -- i)
#define IOS ios::sync_with_stdio(false), cin.tie(nullptr);
using namespace std;
typedef long long ll;
inline ll read() {
ll s = 0;
bool fl = false;
char ch = (char) getchar();
while (!isdigit(ch)) {
if (ch == '-')fl = true;
ch = (char) getchar();
}
while (isdigit(ch)) {
s = s * 10 + (ch ^ 48);
ch = (char) getchar();
}
return fl ? -s : s;
}
const int mod = 1000000000 + 7;
const int itinf = 1000000999;
const ll llinf = 2e18;
const int N = 500099;
struct DS{
multiset<ll>sl, sr;
ll suml, sumr;
DS(){suml = sumr = 0;}
void adjust(){
ll n = sl.size() + sr.size();// l fl n / 2, r ce n / 2;
while(sl.size() < n / 2){
suml += *sr.begin();
sumr -= *sr.begin();
sl.emplace(*sr.begin());
sr.erase(sr.begin());
}
while(sl.size() > n / 2){
sumr += *(-- sl.end());
suml -= *(-- sl.end());
sr.emplace(*(-- sl.end()));
sl.erase(-- sl.end());
}
}
void insert(ll x){
if(sr.empty() || x >= *sr.begin()){
sr.emplace(x);
sumr += x;
}
else{
sl.emplace(x);
suml += x;
}
adjust();
}
void del(ll x){
if(sl.contains(x)){
suml -= x;
sl.erase(sl.find(x));
}
if(sr.contains(x)){
sumr -= x;
sr.erase(sr.find(x));
}
adjust();
}
};
void solve() {
ll n = read(), k = read();
vector<ll>a(n);
irep(i, 0, n - 1)
a[i] = read() - i;
ll ans = 0;
ll l = 0, r = 0;
DS u;
while(r <= n){
ll sr = u.sumr - u.suml;
if((r - l) % 2 == 1)sr -= *u.sr.begin();
if(sr <= k){
ans = max(ans, r - l);
u.insert(a[r ++]);
}
else{
u.del(a[l ++]);
}
}
cout << min(ans, n) << '\n';
}
int main() {
// IOS
int T = read();
while (T--) {
solve();
}
return 0;
}
//7 1 3 2 0 6 1
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3612kb
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: 123ms
memory: 6364kb
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 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 4 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 3 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 4 5 8 3 7 3 3 3...
result:
wrong answer 11101st lines differ - expected: '40384', found: '40385'