제출 #1204880

#제출 시각아이디문제언어결과실행 시간메모리
1204880LucaIlieGrowing Vegetables is Fun 5 (JOI24_vegetables5)C++20
0 / 100
5095 ms50088 KiB
#include <bits/stdc++.h> using namespace std; struct AINT { int ls, rs; vector<int> aint, lazy; void init(int l, int r) { aint.clear(); lazy.clear(); aint.resize(4 * (r - l + 1)); lazy.resize(4 * (r - l + 1)); ls = l; rs = r; } void propag(int v, int l, int r) { aint[v] += lazy[v]; if (l != r) { lazy[v * 2 + 1] += lazy[v]; lazy[v * 2 + 2] += lazy[v]; } lazy[v] = 0; } void update(int v, int l, int r, int lu, int ru, int x) { propag(v, l, r); if (l > ru || r < lu) return; if (lu <= l && r <= ru) { // printf("NU %d %d %d\n", l, r, x); lazy[v] += x; propag(v, l, r); return; } int mid = (l + r) / 2; update(v * 2 + 1, l, mid, lu, ru, x); update(v * 2 + 2, mid + 1, r, lu, ru, x); aint[v] = min(aint[v * 2 + 1], aint[v * 2 + 2]); } void update(int l, int r, int x) { update(0, ls, rs, l, r, x); } int query(int v, int l, int r, int lq, int rq) { if (l > rq || r < lq) return (int)1e9; if (lq <= l && r <= rq) return aint[v]; int mid = (l + r) / 2; return min(query(v * 2 + 1, l, mid, lq, rq), query(v * 2 + 2, mid + 1, r, lq, rq)); } int query(int l, int r) { return query(0, ls, rs, l, r); } }; 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 greaterInOtherSide[2 * MAX_N + 1]; bool startB[2 * MAX_N + 1], startC[2 * MAX_N + 1]; AINT rp, pl; 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 updatePos(int i, int p) { // printf("updare pos %d %d\n", i, p); rp.update(i, i, rightPos[i] - p); pl.update(i, i, p - leftPos[i]); } void updateRangePos(int l, int r, int x) { if (l > r) return; // printf("updare range pos %d %d %d\n", l, r, x); rp.update(l, r, -x); pl.update(l, r, +x); } void checkPositionsForColor(int d, int b[], bool start[]) { // printf("FAC %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++; greaterInOtherSide[i] = j; } j = n + 1; for (int i = n + 1; i <= 2 * n; i++) { while (j - 1 >= 1 && a[j - 1] > a[i]) j--; greaterInOtherSide[i] = j; } // for (int i = 1; i <= 2 * n; i++) // printf("%d %d %d\n", leftPos[i], rightPos[i], greaterInOtherSide[i]); // printf("\n"); rp.init(1, 2 * n); pl.init(1, 2 * n); for (int i = 1; i <= n; i++) updatePos(i, i); for (int s = 1; s <= n; s++) { start[s] = (rp.query(s, s + n - 1) >= 0 && pl.query(s, s + n - 1) >= 0); int t = s + n; updateRangePos(s + 1, min(t - 1, greaterInOtherSide[s]), -1); updatePos(t, max(1, greaterInOtherSide[t] - s)); updateRangePos(max(s + 1, greaterInOtherSide[t]), t - 1, +1); } start[n + 1] = (rp.query(n + 1, 2 * n) >= 0 && pl.query(n + 1, 2 * n) >= 0); rp.init(1, 2 * n); pl.init(1, 2 * n); for (int i = n + 1; i <= 2 * n; i++) updatePos(i, 2 * n - i + 1); for (int s = n + 2; s <= 2 * n; s++) { int t = s - n - 1; updateRangePos(greaterInOtherSide[s - 1], t, -1); int pos = 1; for (int i = s; i <= 2 * n; i++) pos += (a[i] <= a[t]); for (int i = 1; i < t; i++) pos += (a[i] <= a[t]); updatePos(t, pos); //updatePos(t, t + 2 * n - max(s - 1, greaterInOtherSide[t])); updateRangePos(s, greaterInOtherSide[t], +1); start[s] = (rp.query(s, 2 * n) >= 0 && rp.query(1, t) >= 0 && pl.query(1, t) >= 0 && pl.query(s, 2 * n) >= 0); } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i = 1; i <= 2 * n; i++) cin >> a[i]; b[0] = -MAX_VAL; for (int i = 1; i <= n; i++) cin >> b[i]; sort(b + 1, b + 1 + n); c[0] = -MAX_VAL; for (int i = 1; i <= n; i++) cin >> c[i]; sort(c + 1, c + 1 + n); int l = -1, r = MAX_VAL; 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...