Submission #1269861

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269861		MateiKing80	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	0 / 100	5092 ms	69508 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;
#define fr first
#define sc second

const int N = 300005;
int mic[N], mare[N], a[N], b[N], n;

bool fct(int k) {
	//iteram dupa numarul de elemente din a bagate in mare
	//alea mari din a o sa fie in principiu in ala mare deja, acolo merge doar daca numarul luate este >= ceva
	//alea mici din a trebuie sa fie in ceva interval numarul de numere
	//same goes for b dar invers
	vector<pii> lra, lrb;
	int cst = 0, cdr = -1;
	for (int i = 0; i < n; i ++) {
		while (cst < n && mic[cst] < a[i] - k)
			cst ++;
		while (cdr < n - 1 && mic[cdr + 1] <= a[i] + k)
			cdr ++;
		lra.push_back({cst, cdr});
	}
	cst = 0, cdr = -1;
	for (int i = 0; i < n; i ++) {
		while (cst < n && mare[cst] < b[i] - k)
			cst ++;
		while (cdr < n - 1 && mare[cdr + 1] <= b[i] + k)
			cdr ++;
		lrb.push_back({cst, cdr});
	}
	int mx = n;
	for (int i = 0; i < n; i ++) {
		if (abs(mic[i] - b[i]) > k || abs(mare[n - i - 1] - a[n - i - 1]) > k) {
			mx = i;
			break;
		}
	}
	//cout << mx << '\n';
	if (mx == n)
		return true;
	set<pii> la, lb, ra, rb;
	for (int i = 0; i < n; i ++) {
		la.insert({lra[i].fr - i, i});
		ra.insert({lra[i].sc - i, i});
		lb.insert({i - lrb[i].sc, i});
		rb.insert({i - lrb[i].fr, i});
	//	cout << lra[i].fr - i << " " << lra[i].sc - i << '\n';
	//	cout << i - lrb[i].sc << " " << i - lrb[i].fr << '\n' << '\n';
	}
	for (int i = 0; i <= mx; i ++) { //nr el bagate de a in mare 
		if ((*la.rbegin()).fr <= i && 
		    (*lb.rbegin()).fr <= i && 
		    (*ra.begin()).fr >= i && 
		    (*rb.begin()).fr >= i)
			return true;
		la.erase({lra[n - i - 1].fr - n + i + 1, n - i - 1});
		ra.erase({lra[n - i - 1].sc - n + i + 1, n - i - 1});
		lb.erase({i - lrb[i].sc, i});
		rb.erase({i - lrb[i].fr, i});
	}
	return false;
}

signed main() {
	cin >> n;
	for (int i = 0; i < n; i ++)
		cin >> mic[i];
	for (int i = n - 1; i >= 0; i --)
		cin >> mare[i];
	for (int i = 0; i < n; i ++)
		cin >> a[i];
	sort(a, a + n);
	for (int i = 0; i < n; i ++)
		cin >> b[i];
	sort(b, b + n);
	
	int pos1 = -1;
	for (int pas = 1 << 30; pas; pas >>= 1)
		if (!fct(pos1 + pas))
			pos1 += pas;
	swap(a, b);
	int pos2 = -1;
	for (int pas = 1 << 30; pas; pas >>= 1)
		if (!fct(pos2 + pas))
			pos2 += pas;
	cout << min(pos1, pos2) + 1 << '\n';
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 5
• Subtask 3: 0 / 21
• Subtask 4: 0 / 37
• Subtask 5: 0 / 33