Submission #149261

#	Time	Username	Problem	Language	Result	Execution time	Memory
149261		bitKOIn (#200)	Crosses on the Grid (FXCUP4_cross)	C++17	100 / 100	200 ms	7656 KiB

cross

#include <vector>
#include <algorithm>
#include <utility>
#include <cstdio>

int st[524288];

long long SelectCross(int K, std::vector<int> I, std::vector<int> O) {
	int N = I.size();
	int NN = 1;
	for (int t = N - 1; t; t >>= 1) NN <<= 1;
	std::vector<std::pair<int, int>> T;
	std::vector<int> CC(O);
	T.reserve(N);
	for (int i = 0; i < N; ++i) T.push_back({-I[i], O[i]});
	std::sort(T.begin(), T.end());
	std::sort(CC.begin(), CC.end());
	CC.erase(std::unique(CC.begin(), CC.end()), CC.end());
	long long ans = 0;

	for (int i = 0; i < N; ++i) {
		int ii = std::lower_bound(CC.begin(), CC.end(), T[i].second) - CC.begin();
		++st[NN + ii];
		for (int p = NN + ii; (p >>= 1); ) st[p] = st[p << 1] + st[p << 1 | 1];
		if (i >= K - 1) {
			int rem = i - K + 1;
			int p = 1;
			for (; p < NN; )
			{
				if (st[p << 1] <= rem) rem -= st[p << 1], p = p << 1 | 1;
				else p <<= 1;
			}
			if (st[p] <= rem) ++p;
			long long ov = CC[p - NN];
			long long dv = ov + T[i].first;
			ans = std::max(ans, ov * ov - dv * dv);
		}
	}
	return ans;
}

• Subtask 1: 8 / 8
• Subtask 2: 55 / 55
• Subtask 3: 37 / 37