Submission #1205166

#TimeUsernameProblemLanguageResultExecution timeMemory
1205166LucaIlieGrowing Vegetables is Fun 5 (JOI24_vegetables5)C++20
30 / 100
5092 ms16660 KiB
#include <bits/stdc++.h> using namespace std; const int MAX_N = 3e5; const int MAX_VAL = 1e9; int n; int a[2 * MAX_N + 1], b[MAX_N + 1], c[MAX_N + 1]; int leftPos[2 * MAX_N + 1], rightPos[2 * MAX_N + 1]; int countLower[2 * MAX_N + 1]; int greaterSide[2 * MAX_N + 1]; int mars[2 * MAX_N + 1]; bool startB[2 * MAX_N + 1], startC[2 * MAX_N + 1]; bool checkMatch() { bool isMatch = false; for (int s = 1; s <= 2 * n; s++) { int t = s + n; if (t > 2 * n) t -= 2 * n; // printf("%d %d %d %d\n", s, t, startB[s], startC[t]); isMatch |= (startB[s] & startC[t]); } // printf("%d\n", isMatch); return isMatch; } void checkPositionsForColor(int d, int b[], bool start[]) { // printf("\n\nFAC %d\n", d); int j; j = 0; for (int i = 1; i <= n; i++) { while (j + 1 <= n && b[j + 1] <= a[i] + d) j++; rightPos[i] = j; } j = 0; for (int i = 2 * n; i >= n + 1; i--) { while (j + 1 <= n && b[j + 1] <= a[i] + d) j++; rightPos[i] = j; } j = 1; for (int i = 1; i <= n; i++) { while (j <= n && b[j] < a[i] - d) j++; leftPos[i] = j; } j = 1; for (int i = 2 * n; i >= n + 1; i--) { while (j <= n && b[j] < a[i] - d) j++; leftPos[i] = j; } j = n + 1; for (int i = n; i >= 1; i--) { while (j + 1 <= 2 * n && a[j + 1] >= a[i]) j++; countLower[i] = 2 * n - j; greaterSide[i] = j; } j = n + 1; for (int i = n + 1; i <= 2 * n; i++) { while (j - 1 >= 1 && a[j - 1] > a[i]) j--; countLower[i] = j - 1; greaterSide[i] = j; } // for (int i = 1; i <= 2 * n; i++) // printf("%d %d %d %d\n", leftPos[i], rightPos[i], countLower[i], greaterSide[i]); // printf("\n"); // for (int i = 0; i <= 2 * n; i++) mars[i] = 0; for (int i = 1; i <= n; i++) { int l, r; int t = greaterSide[i] - n; if (i - t >= leftPos[i]) r = i; else r = min(i, i - leftPos[i] + 1); if (i - t > rightPos[i]) l = n + 1; else l = max(1, i - rightPos[i] + 1); if (l > r) continue; mars[l]++; mars[r + 1]--; } for (int i = n + 1; i <= 2 * n; i++) { int l, r; int t = greaterSide[i]; if (n - i + t >= leftPos[i]) l = i + 1 - n; else l = max(i + 1 - n, leftPos[i] + i - n); if (n - i + t > rightPos[i]) r = 0; else r = min(n, rightPos[i] + i - n); // l = n + 1, r = 0; // for (int s = i + 1 - n; s <= n; s++) { // int p = n - i + max(s, greaterSide[i]); // if (leftPos[i] <= p && p <= rightPos[i]) { // l = min(l, s); // r = max(r, s); // } // } if (l > r) continue; mars[l]++; mars[r + 1]--; } for (int i = n + 1; i <= 2 * n; i++) { int l = 2 * n + 1, r = 0; for (int s = n + 1; s <= i; s++) { int p = n - i + min(s, n + 1 + countLower[i]); // printf("%d %d->%d\n", i, s, p); if (leftPos[i] <= p && p <= rightPos[i]) { l = min(l, s); r = max(r, s); } } if (l > r) continue; mars[l]++; mars[r + 1]--; } for (int i = 1; i <= n; i++) { int l = 2 * n + 1, r = 0; for (int s = n + i + 1; s <= 2 * n; s++) { int p = i + min(2 * n + 1 - s, countLower[i]); // printf("%d %d->%d\n", i, s, p); if (leftPos[i] <= p && p <= rightPos[i]) { l = min(l, s); r = max(r, s); } } if (l > r) continue; mars[l]++; mars[r + 1]--; } for (int i = 1; i <= 2 * n; i++) { mars[i] += mars[i - 1]; start[i] = (mars[i] == n); // printf("%d %d\n", mars[i], start[i]); } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int maxval = 0; cin >> n; for (int i = 1; i <= 2 * n; i++) { cin >> a[i]; maxval = max(maxval, a[i]); } b[0] = -MAX_VAL; for (int i = 1; i <= n; i++) { cin >> b[i]; maxval = max(maxval, b[i]); } sort(b + 1, b + 1 + n); c[0] = -MAX_VAL; for (int i = 1; i <= n; i++) { cin >> c[i]; maxval = max(maxval, c[i]); } sort(c + 1, c + 1 + n); int l = -1, r = maxval; // l = 1, r = 3; while (r - l > 1) { int d = (l + r) / 2; checkPositionsForColor(d, b, startB); checkPositionsForColor(d, c, startC); if (checkMatch()) r = d; else l = d; } cout << r << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...