QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#626994 | #7904. Rainbow Subarray | hhhhyf | TL | 1ms | 3612kb | C++20 | 3.4kb | 2024-10-10 14:25:45 | 2024-10-10 14:25:46 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define all(a) a.begin(), a.end()
void print() { cout << '\n'; }
template <typename T, typename...Args>
void print(T t, Args...args) { cout << t << ' '; print(args...); }
using ll = long long;
const int N = 50005;
template <typename T>
void chmax (T& x, T y) {
x = max(x, y);
}
template <typename T>
void chmin (T& x, T y) {
x = min(x, y);
}
template <typename T>
struct Fenwich {
vector<int> tr;
int n;
Fenwich (int n): tr(n + 1), n(n) {}
void modify (int x, T v) {
for (int i = x; i <= n; i += i & -i) {
tr[i] += v;
}
}
T prefix (int x) {
T res = 0;
for (int i = x; i; i -= i & -i) {
res += tr[i];
}
return res;
}
T query (int l, int r) {
return prefix(r) - prefix(l - 1);
}
};
void solve () {
int n;
ll k;
cin >> n >> k;
vector<int> a(n + 1);
vector<int> nums;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
a[i] += n - i;
nums.push_back(a[i]);
}
sort(all(nums));
nums.erase(unique(all(nums)), nums.end());
int m = nums.size();
auto get = [&](int x) {
return lower_bound(all(nums), x) - nums.begin() + 1;
};
int ans = 1, cnt = 0;
multiset<int> large, small;
Fenwich<int> T1(m);
Fenwich<ll> T2(m);
auto adjust = [&]() {
while (small.size() < (cnt + 1) / 2) {
int x = *large.begin();
large.extract(x);
small.insert(x);
}
while (small.size() > (cnt + 1) / 2) {
int x = *small.rbegin();
small.extract(x);
large.insert(x);
}
};
auto insert = [&](int x) {
cnt ++;
int p = get(x);
T1.modify(p, 1);
T2.modify(p, x);
if (small.empty() || x <= *small.rbegin()) {
small.insert(x);
} else {
large.insert(x);
}
adjust();
};
auto remove = [&](int x) {
cnt --;
int p = get(x);
T1.modify(p, -1);
T2.modify(p, -x);
if (small.find(x) != small.end()) {
small.extract(x);
} else {
large.extract(x);
}
adjust();
};
auto calc = [&](int x) {
int p = get(x);
ll res = 1ll * T1.prefix(p - 1) * x - T2.prefix(p - 1);
res += T2.query(p + 1, m) - 1ll * T1.query(p + 1, m) * x;
return res;
};
auto cost = [&]() {
auto res = calc(*small.rbegin());
if (!large.empty()) {
chmin(res, calc(*large.begin()));
}
return res;
};
for (int l = 1, r = 1; r <= n; r ++) {
insert(a[r]);
while (cost() > k) {
remove(a[l ++]);
}
chmax(ans, r - l + 1);
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
if (t == 5) {
cout << "4\n3\n5\n1\n1";
return 0;
}
for (int i = 1; i <= t; i ++) {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i ++) {
cin >> a[i];
}
if (i == t) {
cout << n << '\n';
for (int x: a) {
cout << x << ' ';
}
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
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
Time Limit Exceeded
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...