QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#551494 | #7904. Rainbow Subarray | potential | TL | 0ms | 3628kb | C++23 | 3.2kb | 2024-09-07 17:07:23 | 2024-09-07 17:07:24 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
# define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
# define int long long
# define lowbit(x) (x & (-x))
# define fi first
# define se second
# define all(x) x.begin(), x.end()
// # define endl '\n'
inline int Read();
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
const int N = 1e6 + 10;
vector <int> v;
int a[N];
int n, m;
int ok(int x){
map <int, int> mp1;
map <int, int> mp2;
priority_queue<int, vector <int>, less <int>> q;// 大根堆 存小值
priority_queue<int, vector <int>, greater <int>> p;// 小根堆 存大值
int k = (x + 1) / 2;
int sum1 = 0, sum2 = 0;
int num1 = 0, num2 = 0;
for(int i = 1; i <= n; i ++){
if(num1 < k){
num1 ++;
sum1 += a[i];
mp1[a[i]] ++;
q.push(a[i]);
}else{
p.push(a[i]);
num2 ++;
sum2 += a[i];
mp2[a[i]] ++;
while(q.size() && mp1[q.top()] == 0) q.pop();
while(p.size() && mp2[p.top()] == 0) p.pop();
while(q.top() > p.top()){
int u, v;
u = q.top(); v = p.top();
q.pop(); p.pop();
mp1[u] --; sum1 -= u;
mp2[v] --; sum2 -= v;
q.push(v);
p.push(u);
mp2[u] ++; sum2 += u;
mp1[v] ++; sum1 += v;
while(q.size() && mp1[q.top()] == 0) q.pop();
while(p.size() && mp2[p.top()] == 0) p.pop();
}
}
if(i > x){
int t = a[i - x];
if(t <= q.top()){
sum1 -= t;
num1 --;
mp1[t] --;
}else{
sum2 -= t;
num2 --;
mp2[t] --;
}
while(p.size() && mp2[p.top()] == 0) p.pop();
while(num1 < k){
int v;
v = p.top();
p.pop();
num1 ++;
num2 --;
mp2[v] --; sum2 -= v;
q.push(v);
mp1[v] ++; sum1 += v;
while(p.size() && mp2[p.top()] == 0) p.pop();
}
}
// cout << i <<" " << sum1 <<" " <<num1 <<" * "<< sum2 <<" "<< num2 <<"\n";
if(i >= x){
// cout <<num1 * q.top() - sum1 + sum2 - num2 * q.top()<<"****\n";
if(num1 * q.top() - sum1 + sum2 - num2 * q.top() <= m) return 1;
}
}
return 0;
}
void Solve(){
cin >> n >> m;
for(int i = 1; i <= n; i ++){
cin >> a[i];
a[i] -= i;
}
int l = 1, r = n, mid;
while(l < r){
mid = l + r + 1 >> 1;
if(ok(mid)) l = mid;
else r = mid - 1;
}
cout << l <<"\n";
// ok(3);
}
signed main(){
IOS;
int T = 1;
cin >> T;
while (T--)
Solve();
return 0;
}
inline int Read(){
int x = 0, f = 1; char c = getchar();
while (c < '0' || c > '9'){ if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3628kb
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...
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...