제출 #745147

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
745147		danikoynov	Measures (CEOI22_measures)	C++14	100 / 100	430 ms	28976 KiB

Main

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 14 / 14
• Subtask 3: 35 / 35
• Subtask 4: 41 / 41