oj.uz

Submission #763821

# Submission time Handle Problem Language Result Execution time Memory
763821 2023-06-22T22:49:29 Z MilosMilutinovic Measures (CEOI22_measures) C++14
59 / 100
 735 ms 39860 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]);
        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: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 328 KB Output is correct
2 Correct 7 ms 212 KB Output is correct
3 Correct 7 ms 212 KB Output is correct
4 Correct 7 ms 332 KB Output is correct
5 Correct 7 ms 212 KB Output is correct
6 Correct 6 ms 212 KB Output is correct
7 Correct 7 ms 332 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 328 KB Output is correct
2 Correct 7 ms 212 KB Output is correct
3 Correct 7 ms 212 KB Output is correct
4 Correct 7 ms 332 KB Output is correct
5 Correct 7 ms 212 KB Output is correct
6 Correct 6 ms 212 KB Output is correct
7 Correct 7 ms 332 KB Output is correct
8 Correct 7 ms 340 KB Output is correct
9 Correct 690 ms 1084 KB Output is correct
10 Correct 729 ms 1088 KB Output is correct
11 Correct 627 ms 1092 KB Output is correct
12 Correct 735 ms 1084 KB Output is correct
13 Correct 622 ms 1088 KB Output is correct
14 Correct 658 ms 1100 KB Output is correct
15 Correct 668 ms 1088 KB Output is correct
16 Correct 627 ms 1088 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 37640 KB Output is correct
2 Correct 331 ms 39572 KB Output is correct
3 Correct 310 ms 39628 KB Output is correct
4 Correct 297 ms 37456 KB Output is correct
5 Correct 312 ms 38732 KB Output is correct
6 Correct 299 ms 37756 KB Output is correct
7 Correct 302 ms 38780 KB Output is correct
8 Correct 299 ms 37592 KB Output is correct
9 Correct 298 ms 37340 KB Output is correct
10 Correct 309 ms 39860 KB Output is correct
11 Correct 300 ms 38196 KB Output is correct
12 Correct 309 ms 39288 KB Output is correct
13 Correct 299 ms 37452 KB Output is correct
14 Correct 310 ms 39332 KB Output is correct
15 Correct 305 ms 39160 KB Output is correct
16 Correct 307 ms 37456 KB Output is correct
17 Correct 303 ms 38732 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 37640 KB Output is correct
2 Correct 331 ms 39572 KB Output is correct
3 Correct 310 ms 39628 KB Output is correct
4 Correct 297 ms 37456 KB Output is correct
5 Correct 312 ms 38732 KB Output is correct
6 Correct 299 ms 37756 KB Output is correct
7 Correct 302 ms 38780 KB Output is correct
8 Correct 299 ms 37592 KB Output is correct
9 Correct 298 ms 37340 KB Output is correct
10 Correct 309 ms 39860 KB Output is correct
11 Correct 300 ms 38196 KB Output is correct
12 Correct 309 ms 39288 KB Output is correct
13 Correct 299 ms 37452 KB Output is correct
14 Correct 310 ms 39332 KB Output is correct
15 Correct 305 ms 39160 KB Output is correct
16 Correct 307 ms 37456 KB Output is correct
17 Correct 303 ms 38732 KB Output is correct
18 Incorrect 450 ms 38888 KB Output isn't correct
19 Halted 0 ms 0 KB -