1030信心赛
Done
OI
Start at: 2025-10-30 14:00
3.3
hour(s)
Host:
66
非常简单,认真做
/*
sum,id - <=id && >=lim[id]
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
#define int long long
int n, m, x, a[N], tot, sum[N];
int lim[N], cnt, tree[N];
map<int, int>mp;
struct node {
int sum, id;
} p[N];
bool cmp(node a, node b) {
return a.sum < b.sum;
}
int lobit(int x) {
return x & -x;
}
void update(int x) {
for (int i = x + 2; i <= n + 2; i += lobit(i)) {
tree[i]++;
}
}
int query(int x) {
int res = 0;
for (int i = x + 1; i >= 1; i -= lobit(i)) {
res += tree[i];
}
return res;
}
signed main() {
cin >> n >> m >> x;
int l = 1;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
mp[a[i]]++;
if (mp[a[i]] == 1) {
cnt++;
}
if (a[i] >= x)
tot++;
while (cnt > m) {
mp[a[l]]--;
if (mp[a[l]] == 0)
cnt--;
l++;
}
lim[i] = l;
p[i] = {sum[i], i};
}
p[0] = {0, 0};
sort(p, p + n + 1, cmp);
l = 0;
int res = 0;
for (int i = 0; i <= n; i++) {
while (l <= n && p[i].sum - p[l].sum >= x)
update(p[l].id), l++;
if (p[i].id)
res += query(p[i].id) - query(lim[p[i].id] - 1);
}
cout << res * 2 - tot << endl;
return 0;
}
截止16:52成绩表

- Status
- Done
- Rule
- OI
- Problem
- 4
- Start at
- 2025-10-30 14:00
- End at
- 2025-10-30 17:19
- Duration
- 3.3 hour(s)
- Host
- Partic.
- 66