QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #619779 | #7904. Rainbow Subarray | Credit | WA | 125ms | 6224kb | C++17 | 3.4kb | 2024-10-07 15:22:15 | 2024-10-07 15:22:17 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define endl '\n'
const int N = 5e5 + 5;
void solve()
{
ll n, k;
cin >> n >> k;
vector<ll>a(n + 1);
for (int i = 1;i <= n;i++) {
cin >> a[i];
a[i] -= i;
}
ll l = 1, r = 1;
ll ans = 1;
multiset<ll>s1, s2;
ll num = 0;
ll cnt = 0;
ll sum1 = 0, sum2 = 0;
while (r <= n) {
if ((r - l + 1) % 2) {
if (s2.empty()) {
s1.insert(a[r]);
sum1 += a[r];
}
else if (*s2.begin() >= a[r]) {
s1.insert(a[r]);
sum1 += a[r];
}
else {
ll x = *s2.begin();
s1.insert(x);
s2.erase(s2.begin());
s2.insert(a[r]);
sum2 -= x;
sum1 += x;
sum2 += a[r];
}
cnt = sum1 - (s1.size()) * *prev(s1.end()) + (s2.size() * *prev(s1.end()) - sum2);
cnt = abs(cnt);
}
else {
if (s2.empty()) {
s2.insert(a[r]);
sum2 += a[r];
}
else if (*prev(s1.end()) > a[r]) {
s2.insert(*prev(s1.end()));
sum2 += *prev(s1.end());
sum1 -= *prev(s1.end());
s1.erase(prev(s1.end()));
s1.insert(a[r]);
sum1 += a[r];
}
else {
s2.insert(a[r]);
sum2 += a[r];
}
cnt = min((sum1 - (s1.size()) * *prev(s1.end()) + (s2.size() * *prev(s1.end()) - sum2)), (sum1 - (s1.size()) * *s2.begin() + (s2.size() * *s2.begin() - sum2)));
cnt = abs(cnt);
}
while (cnt > k && l < r) {
if ((s1.size() + s2.size()) & 1) {
if (s1.find(a[l]) != s1.end()) {
s1.erase(s1.find(a[l]));
sum1 -= a[l];
}
else {
s2.erase(s2.find(a[l]));
sum2 -= a[l];
s2.insert(*prev(s1.end()));
sum2 += *prev(s1.end());
sum1 -= *prev(s1.end());
s1.erase(prev(s1.end()));
}
// sum -= a[l];
cnt = min((sum1 - (s1.size()) * *prev(s1.end()) + (s2.size() * *prev(s1.end()) - sum2)), (sum1 - (s1.size()) * *s2.begin() + (s2.size() * *s2.begin() - sum2)));
cnt = abs(cnt);
}
else {
if (s1.find(a[l]) != s1.end()) {
s1.erase(s1.find(a[l]));
sum1 -= a[l];
sum1 += *s2.begin();
sum2 -= *s2.begin();
s1.insert(*s2.begin());
s2.erase(s2.begin());
}
else {
sum2 -= a[l];
s2.erase(s2.find(a[l]));
}
cnt = sum1 - (s1.size()) * *prev(s1.end()) + (s2.size() * *prev(s1.end()) - sum2);
cnt = abs(cnt);
}
l++;
}
ans = max(ans, (r - l + 1));
r++;
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3836kb
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: 125ms
memory: 6224kb
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 3 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 4 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 4 3 3...
result:
wrong answer 69th lines differ - expected: '2', found: '3'