QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#305981 | #7904. Rainbow Subarray | Nicolas125841 | WA | 138ms | 6828kb | C++17 | 3.4kb | 2024-01-16 07:43:03 | 2024-01-16 07:43:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define ABS(x) ((x) > 0 ? (x) : -(x))
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
ll k;
cin >> k;
vi a(n);
for(int i = 0; i < n; i++) {
cin >> a[i];
}
ll used = 0, shift = 0, abs = 0, ans = 1;
vector<ll> srel;
map<ll, ll> below, middle, above;
const auto center = [&]() {
if((ll)above.size() - (ll)below.size() - (ll)middle.size() > 0) {
ll delta = above.begin()->first + shift;
abs -= delta;
shift -= delta;
used -= ((ll)above.size() - (ll)below.size() - (ll)middle.size()) * delta;
if(middle.size()) {
below[middle.begin()->first] += middle.begin()->second;
middle.clear();
}
middle[above.begin()->first] = above.begin()->second;
above.erase(above.begin());
} else if((ll)below.size() - (ll)above.size() - (ll)middle.size() > 0) {
ll delta = below.rbegin()->first + shift;
abs -= delta;
shift -= delta;
used -= ((ll)below.size() - (ll)above.size() - (ll)middle.size()) * -delta;
if(middle.size()) {
above[middle.begin()->first] += middle.begin()->second;
middle.clear();
}
middle[below.rbegin()->first] = below.rbegin()->second;
below.erase(below.rbegin()->first);
}
};
abs = a[0];
middle[0]++;
srel.push_back(0);
for(ll l = -1, r = 1; r < n; r++) {
ll diff = abs + 1 - a[r];
if(diff > 0) {
above[diff - shift]++;
used += diff;
abs++;
srel.push_back(diff - shift);
} else if(diff == 0) {
middle[diff - shift]++;
used += diff;
abs++;
srel.push_back(diff - shift);
} else {
below[diff - shift]++;
used += -diff;
abs++;
srel.push_back(diff - shift);
}
center();
if(used > k) {
l++;
used -= ABS(srel[l] + shift);
if(srel[l] + shift > 0) {
above[srel[l]]--;
if(!above[srel[l]])
above.erase(srel[l]);
} else if(srel[l] + shift == 0) {
middle[srel[l]]--;
if(!middle[srel[l]])
middle.erase(srel[l]);
} else {
below[srel[l]]--;
if(!below[srel[l]])
below.erase(srel[l]);
}
center();
}
assert(used >= 0);
if(used <= k)
ans = max(ans, r - l);
}
cout << ans << "\n";
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3572kb
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: 138ms
memory: 6828kb
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 11014th lines differ - expected: '410', found: '409'