#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) continue;
int tt = worm(root[i], k);
mav = max(mav, (ll)y[tt] * y[tt] - (y[tt] - vec[i].first) * ((ll)y[tt] - vec[i].first));
}
return mav;
}
Compilation message
hiccup.cpp:1:10: fatal error: cross.h: No such file or directory
#include "cross.h"
^~~~~~~~~
compilation terminated.
