P8475 「GLR-R3」雨水

评测记录

求助大佬，为什么会有MLE?

代码：

#include <cstdio> // scanf
#include <algorithm>
using namespace std;

const int MAXN = 1e7+5; // Set a right value according to your solution.
long long n, a[MAXN];

unsigned long long cnt; long long top;

struct item {long long v; long long p; bool operator<(const item A) const{return v == A.v ? p > A.p : v < A.v;}} b[MAXN];

namespace Generator {
	
	unsigned long long k1, k2;
	int thres;
	
	inline unsigned long long xorShift128Plus() {
		unsigned long long k3 = k1, k4 = k2;
		k1 = k4, k3 ^= (k3 << 23), k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
		return k2 + k4;
	}
	
	inline void generate() {
		for (int i = 1; i <= n; ++i) {
			a[i] = xorShift128Plus() % thres;
		}
	}
	
} // namespace Generator.

int main() {
	scanf("%lld", &n);
	scanf("%llu %llu %d", &Generator::k1, &Generator::k2, &Generator::thres);
	Generator::generate();
	// Now array a[1..n] represents the sequence A in the statement.
	for (int i = 1; i <= n; i++) b[i].v = a[i], b[i].p = i;
	int I, sw = 0; I = top = 1;
	sort(b + 1, b + 1 + n);
	while (I <= n && cnt < 1llu * n / 2) {
		long long tmp = top;
		while ((I >= b[top].p || b[top].p < sw || a[I] <= a[b[top].p]) && top <= n) top++;
		if (top > n) {top = tmp; I++; continue;}
		swap(a[I], a[b[top].p]);
		I = sw = b[top].p + 1;
		cnt++; top++;
	}
	cnt = 0;
	for (int i = 1; i <= n; i++) {
		cnt += i * a[i];
	}
	printf("%llu\n", cnt);
	return 0;
}