Submission #150146

#	Time	Username	Problem	Language	Result	Execution time	Memory
150146		오리버스부릉부릉 (#200)	Crosses on the Grid (FXCUP4_cross)	C++17	100 / 100	344 ms	71532 KiB

cross

#include "cross.h"
#include <algorithm>
#include <functional>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

struct node {
	int l, r, val, ori;
} tree[5000001];

pii vec[200001];
int y[200001];
int root[200001];
int szz = 1, num = 0;

// 1~n�����ϱ�.
int init(int l, int r) {
	int now = num++;

	if (l != r) {
		tree[now].l = init(l, (l + r) / 2);
		tree[now].r = init((l + r) / 2 + 1, r);
	}
	else tree[now].ori = l;

	return now;
}

// ++1 g�ϴ� ����.
int update(int i, int l, int r, int le, int ri) {
	if (l > ri || r < le) return i;

	int now = num++;
	if (le == ri) {
		tree[now].val = tree[i].val + 1;
		tree[now].ori = le;
		return now;
	}

	int p = update(tree[i].l, l, r, le, (le + ri) / 2);
	int q = update(tree[i].r, l, r, (le + ri) / 2 + 1, ri);

	tree[now] = { p, q, tree[p].val + tree[q].val };
	return now;
}

// worm�ڵ带 ��� �ۼ��ϳ�... ���� �����ʿ� �ִ� �ź��� ���� �ϴµ�..
// �ϴ� root������ ���� üũ�ϰ�.
// ���������� �������� �ش� ��忡�������� Ŀ�� ĥ �� �ִ����� ����ؼ� ����.

int worm(int i, int cnt) {
	if (tree[i].l == 0) return tree[i].ori;
	if (tree[tree[i].r].val >= cnt) return worm(tree[i].r, cnt);
	else return worm(tree[i].l, cnt - tree[tree[i].r].val);
}

ll SelectCross(int k, std::vector<int> in, std::vector<int> o) {
	int n = in.size();
	while (szz <= n) szz *= 2;

	for (int ii = 1; ii <= n; ii++) {
		vec[ii] = { in[ii - 1], o[ii - 1] };
		y[ii] = o[ii - 1];
	}
	sort(vec + 1, vec + 1 + n);
	sort(y + 1, y + n + 1);

	root[0] = init(1, n);

	ll mav = 0;
	for (int i = n; i >= 1; i--) {
		int t = lower_bound(y + 1, y + n + 1, vec[i].second) - y;
		root[i] = update(root[(i + 1 > n) ? 0 : i + 1], t, t, 1, n);

		if (n - k < i - 1) continue;
		int tt = worm(root[i], k);
		mav = max(mav, (ll)y[tt] * y[tt] - ((ll)y[tt] - vec[i].first) * (y[tt] - vec[i].first));
	}

	return mav;
}

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