QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #277293 | #7904. Rainbow Subarray | Rikkual | TL | 1764ms | 20156kb | C++14 | 2.6kb | 2023-12-06 17:27:08 | 2024-06-09 00:01:00 |
Judging History
answer
#include<bits/stdc++.h>
#define Heap_PII priority_queue<PII, vector<PII>, greater<PII>>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
#define _rep(i, a, b) for(int i = (a); i >= (b); i--)
#define out(x) cout << ((x) ? "YES" : "NO") << endl
#define mod(x, P) (((x) % (P) + (P)) % (P))
#define ULL unsigned long long
#define PII pair<int, int>
#define PLL pair<LL, LL>
#define lowbit(x) (x & -x)
#define LL long long
#define pb push_back
#define gcd __gcd
#define Big __int128
#define endl "\n"
#define x first
#define y second
#define int LL
using namespace std;
const int N = 5e5 + 10, M = 1e4 + 10, INF = 1e9, P = 13331;
int n, m;
struct node{
int l, r;
int v, sum;
void init(){
l = r = v = sum = 0;
}
}tr[N * 40];
int root, a[N], idx;
void pushup(int u){
tr[u].v = tr[tr[u].l].v + tr[tr[u].r].v;
tr[u].sum = tr[tr[u].l].sum + tr[tr[u].r].sum;
}
void modify(int &u, int l, int r, int x, int c){
if(!u) tr[u = ++idx].init();
if(l == r) tr[u].v += c, tr[u].sum += l * c;
else{
int mid = l + r >> 1;
if(x <= mid) modify(tr[u].l, l, mid, x, c);
else modify(tr[u].r, mid + 1, r, x, c);
pushup(u);
}
}
int sum(int u, int l, int r, int L, int R){
if(!u) return 0;
if(L <= l && r <= R) return tr[u].v;
int mid = l + r >> 1, ans = 0;
if(L <= mid) ans += sum(tr[u].l, l, mid, L, R);
if(R > mid) ans += sum(tr[u].r, mid + 1, r, L, R);
return ans;
}
int SUM(int u, int l, int r, int L, int R){
if(!u) return 0;
if(L <= l && r <= R) return tr[u].sum;
int mid = l + r >> 1, ans = 0;
if(L <= mid) ans += SUM(tr[u].l, l, mid, L, R);
if(R > mid) ans += SUM(tr[u].r, mid + 1, r, L, R);
return ans;
}
int query(int u, int l, int r, int k){
if(l == r) return l;
int mid = l + r >> 1;
if(tr[tr[u].l].v < k) return query(tr[u].r, mid + 1, r, k - tr[tr[u].l].v);
return query(tr[u].l, l, mid, k);
}
void solve(){
cin >> n >> m;
_for(i, 1, n) cin >> a[i];
_for(i, 1, n) a[i] += 1e15 - i;
root = idx = 0;
int L = 1, R = 1, ans = 0;
while(L <= n){
while(R <= n){
modify(root, 0, 2e15, a[R], 1);
int l = query(root, 0, 2e15, (R - L) / 2 + 1);
int t = sum(root, 0, 2e15, 0, l) * l - SUM(root, 0, 2e15, 0, l) + SUM(root, 0, 2e15, l, 2e15) - sum(root, 0, 2e15, l, 2e15) * l;
if(t > m){
modify(root, 0, 2e15, a[R], -1);
break;
}
R++;
}
ans = max(ans, R - L);
modify(root, 0, 2e15, a[L++], -1);
}
cout << ans << endl;
}
signed main(){
IOS;
int T = 1;
cin >> T;
while(T--){
solve();
}
return 0;
}
/*
1
7 5
7 2 5 5 4 11 7
*/
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5640kb
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: 0
Accepted
time: 1764ms
memory: 20156kb
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:
ok 11102 lines
Test #3:
score: -100
Time Limit Exceeded
input:
1 500000 17244641009859 54748096 75475634 204928248 276927808 84875072 103158867 27937890 322595515 186026685 45468307 69240390 139887597 188586447 373764525 121365644 310156469 185188306 60350786 211308832 384695957 370562147 208427221 35937909 267590963 126478310 275357775 55361535 335993561 36696...