oj.uz

Submission #763819

# Submission time Handle Problem Language Result Execution time Memory
763819 2023-06-22T22:43:00 Z MilosMilutinovic Measures (CEOI22_measures) C++14
59 / 100
 745 ms 39868 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e5 + 10;
const int M = 8 * N;
const ll inf = 0x3f3f3f3f3f3f3f3f;
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;
        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);
    }
}
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, [&](int i, int j) { return b[i] < b[j]; } );
    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]);
        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));
        ans = max(ans, L.query(1, 1, m, 1, pos[i] - 1) + R.query(1, 1, m, pos[i], pos[i]));
        ans = max(ans, L.query(1, 1, m, pos[i], 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] + 1, 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:27:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'void LazySegmentTree::inc(int, int, int, int, int, long long int)':
Main.cpp:41:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'void LazySegmentTree::upd(int, int, int, int, long long int)':
Main.cpp:52:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'long long int LazySegmentTree::query(int, int, int, int, int)':
Main.cpp:68:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:126:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |     scanf("%d%d%d", &n, &m, &d);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:128:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~
Main.cpp:131:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |         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 8 ms 340 KB Output is correct
4 Correct 7 ms 340 KB Output is correct
5 Correct 7 ms 340 KB Output is correct
6 Correct 7 ms 340 KB Output is correct
7 Correct 7 ms 212 KB Output is correct
8 Correct 7 ms 340 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 8 ms 340 KB Output is correct
4 Correct 7 ms 340 KB Output is correct
5 Correct 7 ms 340 KB Output is correct
6 Correct 7 ms 340 KB Output is correct
7 Correct 7 ms 212 KB Output is correct
8 Correct 7 ms 340 KB Output is correct
9 Correct 682 ms 1092 KB Output is correct
10 Correct 731 ms 1108 KB Output is correct
11 Correct 630 ms 1092 KB Output is correct
12 Correct 745 ms 1108 KB Output is correct
13 Correct 624 ms 1108 KB Output is correct
14 Correct 665 ms 1108 KB Output is correct
15 Correct 672 ms 1108 KB Output is correct
16 Correct 634 ms 1092 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 37736 KB Output is correct
2 Correct 319 ms 39596 KB Output is correct
3 Correct 309 ms 39548 KB Output is correct
4 Correct 292 ms 37380 KB Output is correct
5 Correct 309 ms 38824 KB Output is correct
6 Correct 298 ms 37836 KB Output is correct
7 Correct 330 ms 38728 KB Output is correct
8 Correct 291 ms 37496 KB Output is correct
9 Correct 306 ms 37576 KB Output is correct
10 Correct 308 ms 39868 KB Output is correct
11 Correct 297 ms 38220 KB Output is correct
12 Correct 296 ms 39180 KB Output is correct
13 Correct 289 ms 37404 KB Output is correct
14 Correct 302 ms 39496 KB Output is correct
15 Correct 295 ms 39156 KB Output is correct
16 Correct 302 ms 37436 KB Output is correct
17 Correct 297 ms 38752 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 37736 KB Output is correct
2 Correct 319 ms 39596 KB Output is correct
3 Correct 309 ms 39548 KB Output is correct
4 Correct 292 ms 37380 KB Output is correct
5 Correct 309 ms 38824 KB Output is correct
6 Correct 298 ms 37836 KB Output is correct
7 Correct 330 ms 38728 KB Output is correct
8 Correct 291 ms 37496 KB Output is correct
9 Correct 306 ms 37576 KB Output is correct
10 Correct 308 ms 39868 KB Output is correct
11 Correct 297 ms 38220 KB Output is correct
12 Correct 296 ms 39180 KB Output is correct
13 Correct 289 ms 37404 KB Output is correct
14 Correct 302 ms 39496 KB Output is correct
15 Correct 295 ms 39156 KB Output is correct
16 Correct 302 ms 37436 KB Output is correct
17 Correct 297 ms 38752 KB Output is correct
18 Incorrect 471 ms 38616 KB Output isn't correct
19 Halted 0 ms 0 KB -