제출 #763823

#제출 시각아이디문제언어결과실행 시간메모리
763823MilosMilutinovicMeasures (CEOI22_measures)C++14
100 / 100
738 ms41756 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int N = 3e5 + 10; const int M = 16 * N; const ll inf = 5e17; int n, m, d, a[N], b[N], ord[N], pos[N]; struct LazySegmentTree { ll mx[M], lzy[M]; void push(int x) { if ((x << 1 | 1) >= M) { lzy[x] = 0; return; } mx[x << 1] += lzy[x]; mx[x << 1 | 1] += lzy[x]; lzy[x << 1] += lzy[x]; lzy[x << 1 | 1] += lzy[x]; lzy[x] = 0; } void pull(int x) { mx[x] = max(mx[x << 1], mx[x << 1 | 1]); } void init(int x, int l, int r) { mx[x] = -inf; lzy[x] = 0; if (l == r) return; int mid = l + r >> 1; init(x << 1, l, mid); init(x << 1 | 1, mid + 1, r); } void inc(int x, int l, int r, int ql, int qr, ll v) { if (l > r || l > qr || r < ql || ql > qr) { return; } if (ql <= l && r <= qr) { mx[x] += v; lzy[x] += v; return; } push(x); int mid = l + r >> 1; inc(x << 1, l, mid, ql, qr, v); inc(x << 1 | 1, mid + 1, r, ql, qr, v); pull(x); } void upd(int x, int l, int r, int p, ll v) { push(x); if (l == r) { mx[x] = v; return; } int mid = l + r >> 1; if (p <= mid) { upd(x << 1, l, mid, p, v); } else { upd(x << 1 | 1, mid + 1, r, p, v); } pull(x); } ll query(int x, int l, int r, int ql, int qr) { if (l > r || l > qr || r < ql || ql > qr) { return -inf; } if (ql <= l && r <= qr) { return mx[x]; } push(x); int mid = l + r >> 1; ll lx = query(x << 1, l, mid, ql, qr); ll rx = query(x << 1 | 1, mid + 1, r, ql, qr); pull(x); return max(lx, rx); } } L, R; struct Fenwick { int c[N]; void init() { for (int i = 0; i < N; i++) c[i] = 0; } void modify(int p, int x) { for (; p < N; p += p & -p) c[p] += x; } int query(int p) { int s = 0; for (; p > 0; p -= p & -p) s += c[p]; return s; } int query(int l, int r) { return query(r) - query(l - 1); } } fenw; bool check(long double x) { long double prv = a[1] - x; for (int i = 2; i <= n; i++) { long double L = a[i] - x; long double R = a[i] + x; long double pos = max(L, prv + d); if (pos > R) { return false; } prv = pos; } return true; } void solveBrute() { for (int i = 1; i <= m; i++) { a[++n] = b[i]; sort(a + 1, a + n + 1); long long low = 0, high = 1e17, ans = 1e17; while (low <= high) { long long mid = low + (high - low) / 2; if (check(mid)) { ans = mid; high = mid - 1; } else { low = mid + 1; } } if (ans > 0 && check(ans - 0.5)) printf("%lld.5 ", ans - 1); else printf("%lld ", ans); } } bool cmp(int i, int j) { if (b[i] != b[j]) return b[i] < b[j]; else return i < j; } int main() { scanf("%d%d%d", &n, &m, &d); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } for (int i = 1; i <= m; i++) { scanf("%d", &b[i]); ord[i] = i; } if (m <= 10) { solveBrute(); return 0; } sort(ord + 1, ord + m + 1, cmp); for (int i = 1; i <= m; i++) { pos[ord[i]] = i; } L.init(1, 1, m); R.init(1, 1, m); fenw.init(); ll ans = 0; for (int i = 1; i <= m; i++) { fenw.modify(pos[i], +1); L.upd(1, 1, m, pos[i], -fenw.query(pos[i]) * 1ll * d + b[i]); R.upd(1, 1, m, pos[i], +fenw.query(pos[i]) * 1ll * d - b[i]); L.inc(1, 1, m, pos[i] + 1, m, -d); R.inc(1, 1, m, pos[i] + 1, m, +d); ans = max(ans, L.query(1, 1, m, 1, pos[i]) + R.query(1, 1, m, pos[i] + 1, m)); ans = max(ans, L.query(1, 1, m, 1, pos[i] - 1) + R.query(1, 1, m, pos[i], m)); if (ans & 1) { printf("%lld.5 ", ans / 2); } else { printf("%lld " , ans / 2); } } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In member function 'void LazySegmentTree::init(int, int, int)':
Main.cpp:28:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'void LazySegmentTree::inc(int, int, int, int, int, long long int)':
Main.cpp:42:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'void LazySegmentTree::upd(int, int, int, int, long long int)':
Main.cpp:53:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'long long int LazySegmentTree::query(int, int, int, int, int)':
Main.cpp:69:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:133:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |     scanf("%d%d%d", &n, &m, &d);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:135:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~
Main.cpp:138:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |         scanf("%d", &b[i]);
      |         ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...