oj.uz

Submission #763815

# Submission time Handle Problem Language Result Execution time Memory
763815 2023-06-22T22:32:10 Z MilosMilutinovic Measures (CEOI22_measures) C++14
35 / 100
 372 ms 41708 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) {
            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;
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;
    }
    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));
        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:26:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'void LazySegmentTree::inc(int, int, int, int, int, long long int)':
Main.cpp:40:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'void LazySegmentTree::upd(int, int, int, int, long long int)':
Main.cpp:51:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'long long int LazySegmentTree::query(int, int, int, int, int)':
Main.cpp:67:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |     scanf("%d%d%d", &n, &m, &d);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~
Main.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         scanf("%d", &b[i]);
      |         ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 37808 KB Output is correct
2 Correct 276 ms 39648 KB Output is correct
3 Correct 265 ms 41552 KB Output is correct
4 Correct 239 ms 39328 KB Output is correct
5 Correct 241 ms 40688 KB Output is correct
6 Correct 239 ms 39748 KB Output is correct
7 Correct 238 ms 40688 KB Output is correct
8 Correct 238 ms 39516 KB Output is correct
9 Correct 233 ms 39268 KB Output is correct
10 Correct 246 ms 41708 KB Output is correct
11 Correct 243 ms 40140 KB Output is correct
12 Correct 245 ms 41184 KB Output is correct
13 Correct 245 ms 39356 KB Output is correct
14 Correct 241 ms 41332 KB Output is correct
15 Correct 245 ms 41100 KB Output is correct
16 Correct 233 ms 38972 KB Output is correct
17 Correct 245 ms 40676 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 37808 KB Output is correct
2 Correct 276 ms 39648 KB Output is correct
3 Correct 265 ms 41552 KB Output is correct
4 Correct 239 ms 39328 KB Output is correct
5 Correct 241 ms 40688 KB Output is correct
6 Correct 239 ms 39748 KB Output is correct
7 Correct 238 ms 40688 KB Output is correct
8 Correct 238 ms 39516 KB Output is correct
9 Correct 233 ms 39268 KB Output is correct
10 Correct 246 ms 41708 KB Output is correct
11 Correct 243 ms 40140 KB Output is correct
12 Correct 245 ms 41184 KB Output is correct
13 Correct 245 ms 39356 KB Output is correct
14 Correct 241 ms 41332 KB Output is correct
15 Correct 245 ms 41100 KB Output is correct
16 Correct 233 ms 38972 KB Output is correct
17 Correct 245 ms 40676 KB Output is correct
18 Incorrect 372 ms 40652 KB Output isn't correct
19 Halted 0 ms 0 KB -