QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#606876 | #7904. Rainbow Subarray | Kdlyh | WA | 141ms | 10760kb | C++20 | 5.6kb | 2024-10-03 12:49:16 | 2024-10-03 12:49:16 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <stack>
using i64 = long long;
namespace ranges = std::ranges;
#ifdef LOCAL
template <class T, size_t size = std::tuple_size<T>::value> std::string to_debug(T, std::string s = "") requires(not std::ranges::range<T>);
std::string to_debug(auto x) requires requires(std::ostream& os) { os << x; } { return static_cast<std::ostringstream>(std::ostringstream() << x).str(); }
std::string to_debug(std::ranges::range auto x, std::string s = "") requires(not std::is_same_v<decltype(x), std::string>) {
for (auto xi : x) { s += ", " + to_debug(xi); }
return "[" + s.substr(s.empty() ? 0 : 2) + "]";
}
template <class T, size_t size> std::string to_debug(T x, std::string s) requires(not std::ranges::range<T>) {
[&]<size_t... I>(std::index_sequence<I...>) { ((s += ", " + to_debug(get<I>(x))), ...); }(std::make_index_sequence<size>());
return "(" + s.substr(s.empty() ? 0 : 2) + ")";
}
#define debug(...) std::cerr << __LINE__ << ": (" #__VA_ARGS__ ") = " << to_debug(std::tuple(__VA_ARGS__)) << "\n"
#else
#define debug(x...)
#endif
bool dbgL2{};
#define int long long
template <typename T>
class DualHeap {
private:
// 大根堆,维护较小的一半元素
std::priority_queue<T> small;
// 小根堆,维护较大的一半元素
std::priority_queue<T, std::vector<T>, std::greater<T>> large;
// 哈希表,记录「延迟删除」的元素,key 为元素,value 为需要删除的次数
std::unordered_map<T, int> delayed;
// small 和 large 当前包含的元素个数,需要扣除被「延迟删除」的元素
int smallSize, largeSize;
public:
i64 smallRes{}, largeRes{};//用来维护
DualHeap() : smallSize(0), largeSize(0) {}
private:
// 不断地弹出 heap 的堆顶元素,并且更新哈希表
template <typename H>
void prune(H& heap)
{
while (not heap.empty()) {
int num = heap.top();
if (delayed.contains(num)) {
delayed[num] -= 1;
if (!delayed[num]) {
delayed.erase(num);
}
if (dbgL2) {debug(num);}
heap.pop();
} else {
break;
}
}
}
// 调整 small 和 large 中的元素个数,使得二者的元素个数满足要求
void makeBalance()
{
if (smallSize > largeSize + 1) {
// small 比 large 元素多 2 个
large.push(small.top());
if (not delayed.contains(small.top())) {
smallRes -= small.top(); largeRes += small.top();
}
small.pop();
smallSize -= 1;
largeSize += 1;
// small 堆顶元素被移除,需要进行 prune
prune(small);
} else if (smallSize < largeSize) {
// large 比 small 元素多 1 个
small.push(large.top());
if (not delayed.contains(large.top())) {
largeRes -= large.top(); smallRes += large.top();
}
large.pop();
smallSize += 1;
largeSize -= 1;
// large 堆顶元素被移除,需要进行 prune
prune(large);
}
}
public:
void insert(const T& num)
{
if (small.empty() or num <= small.top()) {
if (dbgL2) {debug(largeRes, smallRes, num);}
small.push(num); smallRes += num;
if (dbgL2) {debug(largeRes, smallRes, num);}
smallSize += 1;
} else {
large.push(num); largeRes += num;
largeSize += 1;
}
makeBalance();
}
void erase(const T& num)
{
delayed[num] += 1;
if (num <= small.top()) {
smallSize -= 1; smallRes -= num;
if (num == small.top()) {
prune(small);
}
} else {
largeSize -= 1; largeRes -= num;
if (num == large.top()) {
prune(large);
}
}
makeBalance();
}
T getMedian() { return small.top(); }
i64 getRes(int& tot) {
if (tot & 1) {
if (tot == 1) {return 0;}
return largeRes - smallRes + getMedian();
} else {
return largeRes - smallRes;
}
}
i64 tryRes(auto& num, auto& k, int tot) {
insert(num);
if (getRes(tot) <= k) {return true;}
erase(num); return false;
}
};
void solve()
{
#define tests
int n; i64 k; std::cin >> n >> k; std::vector<int> a(n); for (auto& ai : a) {std::cin >> ai; --ai;}
for (int i = 0; i < n; i++) {a[i] -= i;}
DualHeap<int> dheap; int ans{}; for (int L{}, R{}; L < n; L++) {
dheap.insert(a[L]); R = std::max(L + 1, R);
while (R < n and dheap.tryRes(a[R], k, R - L + 1)) {R += 1;}
ans = std::max(ans, R - L); dheap.erase(a[L]);
}
std::cout << ans << "\n";
}
signed main()
{
std::cin.tie(nullptr)->sync_with_stdio(false);
int _(1);
#ifdef tests
std::cin >> _;
#endif
while(_--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3580kb
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: 141ms
memory: 10760kb
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 4 7 2 4 1 4 1 1 2 2 2 7 5 7 7 1 6 5 2 4 3 1 3 7 7 3 4 3 9 3 8 6 6 3 1 5 3 1 2 4 5 2 6 4 1 3 5 1 6 3 5 5 6 1 5 5 3 1 6 3 5 3 2 2 5 2 3 10 1 3 3 2 4 5 1 6 5 5 5 8 5 3 6 3 5 4 8 5 3 5 2 1 5 2 2 3 3 8 1 3 1 2 2 6 3 1 6 8 1 8 4 5 6 6 7 3 8 3 2 8 4 5 5 2 6 2 3 1 5 4 5 2 2 4 1 2 1 2 3 6 3 6 3 3 2...
result:
wrong answer 6th lines differ - expected: '5', found: '4'