ACwing 109. Genius ACM

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9') {
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9') {
		x=x*10+ch-48;
		ch=getchar();
	}
	return x*f;
}
inline void write(int x) {
	if(x < 0)putchar('-'),x = -x;
	if(x > 9)write(x / 10);
	putchar(x % 10 ^ 48);
}
int b[1000001], a[1000001], c[1000001];
int n, m, t;
inline void msort(int l,int mid, int r) {
	int n = l, m = mid, k = l;
	while(n < mid && m <= r) {
		if(a[n] <= a[m]) {
			b[k] = a[n];
			n++;
			k++;
		} else {
			b[k] = a[m];
			k++;
			m++;
		}
	}
	while(n < mid) {
		b[k] = a[n];
		n++;
		k++;
	}
	while(m <= r) {
		b[k] = a[m];
		m++;
		k++;
	}
}
bool check(int l, int mid, int r) {
	for (int i = mid; i <= r; i++)
		a[i] = c[i];
	sort(a + mid + 1, a + r + 1);
	//cout << mid - 1 + 1 << "-" << r << '\n';
	//cout << l << " " << mid - 1 << " " << r - (mid - 1) << '\n';
	msort(l, mid, r);
	//cout << l << "-" << mid - 1 << "&" << mid << "-" << r << '\n';
	int sum = 0;
	for(int i = 1; i <= r - l + 1 >> 1 && i <= m; i++) {
		sum += (b[r - i + 1]- b[l + i - 1]) * (b[r - i + 1]- b[l + i - 1]);
	}
	if(sum <= t) {
		for (int i = l; i <= r; i++) 
			a[i] = b[i];
		return 1;
	} else {
		return 0;
	}
}
signed main() {
	int k = read();
	while (k--) {
		int ans = 0;
		n = read(), m = read(), t = read();
		for (int i = 1; i <= n; i++) {
			c[i] = read();
		}
		int l, r, p = 1;
		l = r = 1;
		a[1] = c[1];
		while (r <= n) {
			if (!p) {
				ans++;
				p = 1;
				l = (++r);
				a[l] = c[l];
			} else {
				if (check(l, r + 1, r + p) && r + p <= n) {
					r += p;
					p <<= 1;
					if (r == n) {
						break;
					}
				} else {
					p >>= 1;
				}
			}
		}
		if(r == n) {
			ans++;
		}
		write(ans);
		puts("");
	}
	return 0;
}

10分求助