QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #636030 | #7904. Rainbow Subarray | wdw | WA | 190ms | 6696kb | C++20 | 3.2kb | 2024-10-12 21:54:07 | 2024-10-12 21:54:09 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
using ll = long long;
using ld = double;
const ll mod = 1e9 + 7;
const ll inf = 1e9;
const int N = 2e5 + 10;
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n + 5);
int ans = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i] -= i;
// cout << a[i] << " ";
}
int l = 0, r = -1;
vector<int> p(n + 5);
multiset<int, less<int>> q2;
multiset<int, greater<int>> q1;
int lx = 1;
int sum1 = 0, sum2 = 0;
for (int i = 1; i <= n; i++) {
if (l <= r && p[l] < i) {
auto y = q1.find(a[p[l]]);
if (y != q1.end()) {
q1.erase(y);
sum1 -= a[p[l]];
if (q1.size() < q2.size()) {
auto y1 = q2.begin();
q1.insert(*y1);
sum1 += *y1;
sum2 -= *y1;
q2.erase(y1);
}
} else {
auto y = q2.find(a[p[l]]);
sum2 -= *y;
q2.erase(y);
if (q1.size() > q2.size() + 1) {
auto y1 = q1.begin();
q2.insert(*y1);
sum1 -= *y1;
sum2 += *y1;
q1.erase(y1);
}
}
l++;
}
int fx = 0;
while (lx <= n) {
ans = max(r - l + 1, ans);
p[++r] = lx++;
q1.insert(a[p[r]]);
sum1 += a[p[r]];
if (q1.size() > q2.size() + 1||(q2.size()&&*q1.begin()>*q2.begin())) {
auto y1 = q1.begin();
sum1 -= *y1;
sum2 += *y1;
q2.insert(*y1);
q1.erase(y1);
}
if (((*q1.begin() * q1.size() - sum1) + (sum2 - *q1.begin() * q2.size())) > k) {
auto y = q1.find(a[p[r]]);
if (y != q1.end()) {
q1.erase(y);
sum1 -= a[p[r]];
if (q1.size() < q2.size()) {
auto y1 = q2.begin();
q1.insert(*y1);
sum1 += *y1;
sum2 -= *y1;
q2.erase(y1);
}
} else {
auto y = q2.find(a[p[r]]);
sum2 -= *y;
q2.erase(y);
if (q1.size() > q2.size() + 1) {
auto y1 = q1.begin();
q2.insert(*y1);
sum1 -= *y1;
sum2 += *y1;
q1.erase(y1);
}
}
r--, lx--;
fx = 1;
}
ans = max(ans, r - l + 1);
if (fx)break;
}
}
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// cout<<fixed<<setprecision(2);
// srand(time(0));
int T = 1;
cin >> T;
while (T--)solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3652kb
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: 190ms
memory: 6696kb
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 2 2 6 5 7 2 4 1 4 1 1 3 2 2 6 8 6 7 1 7 5 2 4 3 1 6 7 7 3 4 3 9 3 8 5 6 3 1 6 3 1 2 4 6 4 6 4 1 4 7 1 6 3 5 6 6 1 7 4 3 1 6 4 4 3 2 2 6 2 3 10 1 4 3 2 4 5 1 6 5 5 5 7 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 6 4 5 6 6 8 4 8 3 2 8 4 5 6 2 6 2 4 1 3 4 5 3 2 4 1 2 1 3 5 8 3 7 3 3 3...
result:
wrong answer 3rd lines differ - expected: '3', found: '2'