Submission #149922

#	Time	Username	Problem	Language	Result	Execution time	Memory
149922		----MIT합격선---- (#200)	Crosses on the Grid (FXCUP4_cross)	C++17	100 / 100	189 ms	8552 KiB

cross

#include "cross.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using ll = long long;
#define ff first
#define ss second

vector<pii> A;
vector<int> xx;
int N;

const int SIZE = 1 << 18;
struct ST {
	int A[SIZE << 1];
	void update(int x, int v) {
		for (x += SIZE; x; x >>= 1) A[x] += v;
	}
	int query(int v) {
		int x = 1;
		while (x < SIZE) {
			if (A[x << 1 | 1] >= v) x = x << 1 | 1;
			else {
				x <<= 1;
				v -= A[x | 1];
			}
		}
		return x - SIZE;
	}
} seg;

		
ll SelectCross(int K, std::vector<int> I, std::vector<int> O) {
	N = I.size();
	for (int i = 0; i < N; ++i) A.emplace_back(I[i], O[i]);
	sort(A.rbegin(), A.rend());
	for (auto i : A) xx.push_back(i.ss);
	sort(xx.begin(), xx.end());
	xx.erase(unique(xx.begin(), xx.end()), xx.end());
	for (auto &i : A) i.ss = lower_bound(xx.begin(), xx.end(), i.ss) - xx.begin();
	int cnt = 0;
	long long ans = 0;
	for (auto i : A) {
		seg.update(i.ss, 1);
		cnt++;
		if (cnt < K) continue;
		ans = max(ans, 2ll * i.ff * xx[seg.query(K)] - (ll) i.ff * i.ff);
	}
	return ans;
}

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