Submission #150991

#	Time	Username	Problem	Language	Result	Execution time	Memory
150991		pichulia	Crosses on the Grid (FXCUP4_cross)	C++17	100 / 100	247 ms	15868 KiB

cross

#include "cross.h"
#include<algorithm>
#define I 262144
using namespace std;
typedef pair<long long, long long> pll;
int n;
pll a[200009];
long long int ax[200009];
long long int bx[200009];
int al;
int bl;
int ms[2 * I];
void update(int i, int v)
{
	i = i + I;
	ms[i] += v;
	i /= 2;
	while (i > 0) {
		ms[i] = ms[i * 2] + ms[i * 2 + 1];
		i /= 2;
	}
}
int find_min(int dep, int m, int ll, int rr) {
	if (dep >= I) return ll;
	if (ms[dep * 2 + 1] >= m) return find_min(dep * 2 + 1, m, (ll + rr) / 2 + 1, rr);
	return find_min(dep * 2, m - ms[dep * 2 + 1], ll, (ll + rr) / 2);
}
long long SelectCross(int m, std::vector<int> aa, std::vector<int> bb) {
	n = aa.size();
	al = bl = 0;
	int i, j, k;
	for (i = 0; i < n; i++) {
		a[i].first = aa[i];
		a[i].second = bb[i];
		ax[al++] = aa[i];
		bx[bl++] = bb[i];
	}
	bx[bl++] = -999999999;
	sort(ax, ax + al); al = unique(ax, ax + al) - ax;
	sort(bx, bx + bl); bl = unique(bx, bx + bl) - bx;
	for (i = 0; i < n; i++) {
		a[i].first = lower_bound(ax, ax + al, a[i].first) - ax;
		a[i].second = lower_bound(bx, bx + bl, a[i].second) - bx;
	}
	sort(a, a + n);
	for (i = 0; i < 2 * I; i++)ms[i] = 0;

	i = n - 1;
	j = 0;
	long long int res = 0;
	for (k = al - 1; k >= 0; k--)
	{
		//printf("%d %d -->\n", k, i);
		while (i >= 0 && a[i].first == k)
		{
			//printf("%lld , update %lld\n", ax[k], a[i].second);
			update(a[i].second, 1);
			i--;
		}
		if (ms[1] >= m)
		{
			j = find_min(1, m, 0, I - 1);
			//printf("%d , %d\n", ms[1], j);
			if (j > 0) {
				long long int x = ax[k];
				long long int y = bx[j];
				long long int cur = 2 * x * y - x * x;
				//printf("%lld %lld  %lld %lld\n", x, y, cur, res);
				res = max(res, cur);
			}
		}
	}

	return res;
}

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