oj.uz

Submission #745147

# Submission time Handle Problem Language Result Execution time Memory
745147 2023-05-19T12:58:33 Z danikoynov Measures (CEOI22_measures) C++14
100 / 100
 430 ms 28976 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;

const int maxn = 4e5 + 10;

ll n, m, a[maxn], b[maxn], D, act[2][maxn], used[maxn];
ll pref[maxn], suff[maxn];
pair < ll, ll > p[maxn];

const ll inf = 1e18;

struct segment_tree
{
    ll tree[4 * maxn], lazy[4 * maxn];

    void build(int root, int left, int right)
    {
        tree[root] = -inf;
        lazy[root] = 0;
        if (left == right)
            return;
            int mid = (left + right) / 2;
        build(root * 2, left, mid);
        build(root * 2 + 1, mid + 1, right);
    }

    void push_lazy(int root, int left, int right)
    {
        tree[root] += lazy[root];
        if (left != right)
        {
            lazy[root * 2] += lazy[root];
            lazy[root * 2 + 1] += lazy[root];
        }
        lazy[root] = 0;
    }

    void point_update(int root, int left, int right, int pos, ll val)
    {
        push_lazy(root, left, right);
        if (left == right)
        {
            tree[root] = val;
            ///cout << "update " << left << " " << right << endl;
            return;
        }

        int mid = (left + right) / 2;
        if (pos <= mid)
        {
            point_update(root * 2, left, mid, pos, val);
            push_lazy(root * 2 + 1, mid + 1, right);
        }
        else
        {
            point_update(root * 2 + 1, mid + 1, right, pos, val);
            push_lazy(root * 2, left, mid);
        }
        tree[root] = max(tree[root * 2], tree[root * 2 + 1]);
    }

    void range_update(int root, int left, int right, int qleft, int qright, ll val)
    {
        push_lazy(root, left, right);
        if (left > qright || right < qleft)
        return;

        if (left >= qleft && right <= qright)
        {
            lazy[root] = val;
            push_lazy(root, left, right);
            return;
        }

        int mid = (left + right) / 2;
        range_update(root * 2, left, mid, qleft, qright, val);
        range_update(root * 2 + 1, mid + 1, right, qleft, qright, val);

        tree[root] = max(tree[root * 2], tree[root * 2 + 1]);
    }

    ll query(int root, int left, int right, int qleft, int qright)
    {
        push_lazy(root, left, right);
        if (left > qright || right < qleft)
        return -inf;

        if (left >= qleft && right <= qright)
            return tree[root];

        int mid = (left + right) / 2;
        return max(query(root * 2, left, mid, qleft, qright),
                   query(root * 2 + 1, mid + 1, right, qleft, qright));
    }
};

segment_tree pref_seg, suff_seg;

int fen[maxn];

void add(int v)
{
    for (int i = v; i <= n + m; i += (i & -i))
        fen[i] ++;
}

int get_sum(int v)
{
    int s = 0;
    for (int i = v; i > 0; i -= (i & -i))
        s += fen[i];
    return s;
}

void solve()
{
    cin >> n >> m >> D;
    for (int i = 1; i <= n; i ++)
        cin >> a[i], p[i] = {a[i], i};
    for (int j = 1; j <= m; j ++)
        cin >> b[j], p[n + j] = {b[j], n + j};

    sort(p + 1, p + n + m + 1);

    for (int i = 1; i <= n + m; i ++)
    {
        if (p[i].second <= n)
        {
            act[0][p[i].second] = i;
        }
        else
        {
            act[1][p[i].second - n] = i;
        }
    }

    pref_seg.build(1, 1, n + m);
    suff_seg.build(1, 1, n + m);
    ll ans = 0;
    for (ll i = 1; i <= n + m; i ++)
    { ll idx;
    if (i <= n)
        idx = act[0][i];
        else
            idx = act[1][i - n];

        ll cnt = get_sum(idx);
        add(idx);

        pref_seg.point_update(1, 1, n + m, idx, + p[idx].first - cnt * D);
        suff_seg.point_update(1, 1, n + m, idx, - p[idx].first + cnt * D);

        //cout << i << " : " << pref[idx] << " " << suff[idx] << " " << cnt << " " << idx << endl;
        pref_seg.range_update(1, 1, n + m, idx + 1, n + m, -D);
        suff_seg.range_update(1, 1, n + m, idx + 1, n + m, +D);
        //pref[idx] = + p[idx].first - cnt * D;
        //suff[idx] = - p[idx].first + cnt * D;
       // used[idx] = 1;
       /** for (int j = idx + 1; j <= n + m; j ++)
        {
            if (!used[j])
                continue;
            pref[j] = pref[j] - D;
            suff[j] = suff[j] + D;
        }*/

        ll mx_pref = -1e18, mx_suff = -1e18;

        mx_pref = pref_seg.query(1, 1, n + m, 1, idx);
        ///ll pot = pref_seg.query(1, 1, n + m, 1, idx);
        mx_suff = suff_seg.query(1, 1, n + m, idx, n + m);
        /**for (int j = 1; j <= idx; j ++)
        {
            if (!used[j])
                continue;
                ///cout << "pref " << suff[idx] + pref[j] << " " << pref[j] << endl;
                mx_pref = max(mx_pref, pref[j]);
            ///ans = max(ans, suff[idx] + pref[j]);
        }
        for (int j = idx; j <= n + m; j ++)
        {
            if (!used[j])
                continue;
                mx_suff = max(mx_suff, suff[j]);
            ///ans = max(ans, pref[idx] + suff[j]);
        }*/
        ans = max(ans, mx_pref + mx_suff);
        ///cout << ans << endl;
        //cout << endl;
        //cout << endl;
        //cout << mx_pref << " :: " << mx_suff << " " << ans << " " << pot <<endl;
        /**if (mx_pref != pot)
        {
            cout << "!!!!!!!!!!!" << endl;
                exit(0);
        }*/
        if (i > n)
        {
            if (ans % 2 == 0)
                cout << ans / 2 << " ";
            else
                cout << ans / 2 << ".5 ";
        }
    }
    cout << endl;
}
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int main()
{
    speed();
    ///freopen("test.txt", "r", stdin);
    solve();
    return 0;
}

Compilation message

Main.cpp: In member function 'void segment_tree::build(int, int, int)':
Main.cpp:22:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   22 |         if (left == right)
      |         ^~
Main.cpp:24:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   24 |             int mid = (left + right) / 2;
      |             ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 402 ms 23836 KB Output is correct
10 Correct 393 ms 25776 KB Output is correct
11 Correct 273 ms 25812 KB Output is correct
12 Correct 302 ms 25676 KB Output is correct
13 Correct 266 ms 25348 KB Output is correct
14 Correct 293 ms 25808 KB Output is correct
15 Correct 395 ms 25120 KB Output is correct
16 Correct 264 ms 25780 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 24812 KB Output is correct
2 Correct 282 ms 28780 KB Output is correct
3 Correct 285 ms 28720 KB Output is correct
4 Correct 279 ms 26428 KB Output is correct
5 Correct 281 ms 27748 KB Output is correct
6 Correct 272 ms 26868 KB Output is correct
7 Correct 271 ms 27836 KB Output is correct
8 Correct 276 ms 26556 KB Output is correct
9 Correct 274 ms 26496 KB Output is correct
10 Correct 276 ms 28876 KB Output is correct
11 Correct 289 ms 27288 KB Output is correct
12 Correct 287 ms 28320 KB Output is correct
13 Correct 274 ms 26464 KB Output is correct
14 Correct 278 ms 28416 KB Output is correct
15 Correct 275 ms 28272 KB Output is correct
16 Correct 266 ms 26228 KB Output is correct
17 Correct 280 ms 27832 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 24812 KB Output is correct
2 Correct 282 ms 28780 KB Output is correct
3 Correct 285 ms 28720 KB Output is correct
4 Correct 279 ms 26428 KB Output is correct
5 Correct 281 ms 27748 KB Output is correct
6 Correct 272 ms 26868 KB Output is correct
7 Correct 271 ms 27836 KB Output is correct
8 Correct 276 ms 26556 KB Output is correct
9 Correct 274 ms 26496 KB Output is correct
10 Correct 276 ms 28876 KB Output is correct
11 Correct 289 ms 27288 KB Output is correct
12 Correct 287 ms 28320 KB Output is correct
13 Correct 274 ms 26464 KB Output is correct
14 Correct 278 ms 28416 KB Output is correct
15 Correct 275 ms 28272 KB Output is correct
16 Correct 266 ms 26228 KB Output is correct
17 Correct 280 ms 27832 KB Output is correct
18 Correct 420 ms 26896 KB Output is correct
19 Correct 430 ms 28516 KB Output is correct
20 Correct 290 ms 28580 KB Output is correct
21 Correct 318 ms 26616 KB Output is correct
22 Correct 358 ms 27012 KB Output is correct
23 Correct 287 ms 26912 KB Output is correct
24 Correct 423 ms 27464 KB Output is correct
25 Correct 278 ms 26452 KB Output is correct
26 Correct 412 ms 26616 KB Output is correct
27 Correct 407 ms 28976 KB Output is correct
28 Correct 362 ms 26884 KB Output is correct
29 Correct 374 ms 28232 KB Output is correct
30 Correct 314 ms 26436 KB Output is correct
31 Correct 315 ms 28460 KB Output is correct
32 Correct 290 ms 28260 KB Output is correct
33 Correct 409 ms 26072 KB Output is correct
34 Correct 316 ms 27836 KB Output is correct