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成绩表

Files

Filename Size
T4.in 526.5 KiB
T4.out 10 Bytes
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