oj.uz

Submission #149166

# Submission time Handle Problem Language Result Execution time Memory
149166 2019-09-01T05:52:18 Z bitKOIn(#3612, gs15120, phsongys) Crosses on the Grid (FXCUP4_cross) C++17
0 / 100
 5 ms 384 KB 
#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], p = p << 1 | 1;
				else p <<= 1;
			}
			if (st[p] <= rem) ++p;
			long long ov = CC[p - NN];
			long long dv = std::max(0LL, ov + T[i].first);
			// fprintf(stderr, "%d %d %d %lld %lld\n", i, p, -T[i].first, ov, dv);
			ans = std::max(ans, ov * ov - dv * dv);
		}
	}
	return ans;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -