oj.uz

Submission #763823

# Submission time Handle Problem Language Result Execution time Memory
763823 2023-06-22T22:53:11 Z MilosMilutinovic Measures (CEOI22_measures) C++14
100 / 100
 738 ms 41756 KB 
#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;
}

Compilation message

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]);
      |         ~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 340 KB Output is correct
2 Correct 7 ms 212 KB Output is correct
3 Correct 9 ms 340 KB Output is correct
4 Correct 7 ms 212 KB Output is correct
5 Correct 7 ms 336 KB Output is correct
6 Correct 6 ms 336 KB Output is correct
7 Correct 7 ms 336 KB Output is correct
8 Correct 7 ms 212 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 340 KB Output is correct
2 Correct 7 ms 212 KB Output is correct
3 Correct 9 ms 340 KB Output is correct
4 Correct 7 ms 212 KB Output is correct
5 Correct 7 ms 336 KB Output is correct
6 Correct 6 ms 336 KB Output is correct
7 Correct 7 ms 336 KB Output is correct
8 Correct 7 ms 212 KB Output is correct
9 Correct 682 ms 1092 KB Output is correct
10 Correct 734 ms 1100 KB Output is correct
11 Correct 648 ms 1092 KB Output is correct
12 Correct 738 ms 1084 KB Output is correct
13 Correct 625 ms 1092 KB Output is correct
14 Correct 668 ms 1088 KB Output is correct
15 Correct 680 ms 1100 KB Output is correct
16 Correct 637 ms 1084 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 37708 KB Output is correct
2 Correct 283 ms 39576 KB Output is correct
3 Correct 278 ms 39500 KB Output is correct
4 Correct 330 ms 37432 KB Output is correct
5 Correct 281 ms 38724 KB Output is correct
6 Correct 282 ms 37820 KB Output is correct
7 Correct 303 ms 38808 KB Output is correct
8 Correct 278 ms 37568 KB Output is correct
9 Correct 272 ms 37444 KB Output is correct
10 Correct 281 ms 39760 KB Output is correct
11 Correct 318 ms 38168 KB Output is correct
12 Correct 281 ms 39136 KB Output is correct
13 Correct 302 ms 37392 KB Output is correct
14 Correct 304 ms 39348 KB Output is correct
15 Correct 297 ms 39144 KB Output is correct
16 Correct 285 ms 37456 KB Output is correct
17 Correct 283 ms 38660 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 37708 KB Output is correct
2 Correct 283 ms 39576 KB Output is correct
3 Correct 278 ms 39500 KB Output is correct
4 Correct 330 ms 37432 KB Output is correct
5 Correct 281 ms 38724 KB Output is correct
6 Correct 282 ms 37820 KB Output is correct
7 Correct 303 ms 38808 KB Output is correct
8 Correct 278 ms 37568 KB Output is correct
9 Correct 272 ms 37444 KB Output is correct
10 Correct 281 ms 39760 KB Output is correct
11 Correct 318 ms 38168 KB Output is correct
12 Correct 281 ms 39136 KB Output is correct
13 Correct 302 ms 37392 KB Output is correct
14 Correct 304 ms 39348 KB Output is correct
15 Correct 297 ms 39144 KB Output is correct
16 Correct 285 ms 37456 KB Output is correct
17 Correct 283 ms 38660 KB Output is correct
18 Correct 441 ms 37800 KB Output is correct
19 Correct 481 ms 41428 KB Output is correct
20 Correct 292 ms 41548 KB Output is correct
21 Correct 332 ms 39544 KB Output is correct
22 Correct 389 ms 39876 KB Output is correct
23 Correct 293 ms 39676 KB Output is correct
24 Correct 433 ms 40244 KB Output is correct
25 Correct 338 ms 39360 KB Output is correct
26 Correct 413 ms 39340 KB Output is correct
27 Correct 456 ms 41756 KB Output is correct
28 Correct 421 ms 39796 KB Output is correct
29 Correct 385 ms 41172 KB Output is correct
30 Correct 352 ms 39240 KB Output is correct
31 Correct 338 ms 41272 KB Output is correct
32 Correct 292 ms 41136 KB Output is correct
33 Correct 470 ms 38996 KB Output is correct
34 Correct 342 ms 40652 KB Output is correct