Submission #1240378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240378		12345678	Measures (CEOI22_measures)	C++20	100 / 100	147 ms	58540 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll nx=4e5+5, inf=4e18;

ll n, m, D, a[nx], b[nx], dp[nx];
vector<pair<ll, int>> srt;

struct segtree
{
    struct node
    {
        ll ans, x, y, cnt;
        node(ll ans=0, ll x=0, ll y=0, ll cnt=0): ans(ans), x(x), y(y), cnt(cnt){}
    } d[4*nx];
    void merge(int l, int r, int i)
    {
        d[i].ans=max({-inf, d[2*i].ans, d[2*i+1].ans, d[2*i].x+(d[2*i+1].y+d[2*i].cnt*D)});
        d[i].x=max({-inf, d[2*i].x, d[2*i+1].x-d[2*i].cnt*D});
        d[i].y=max({-inf, d[2*i].y, d[2*i+1].y+d[2*i].cnt*D});
        d[i].cnt=d[2*i].cnt+d[2*i+1].cnt;
    }
    void build(int l, int r, int i)
    {
        if (l==r) return d[i]=node(-inf, -inf, -inf, 0), void();
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        merge(l, r, i);
    }
    void update(int l, int r, int i, int idx, int x)
    {
        if (idx<l||r<idx) return;
        if (l==r) return d[i]=node(0, x-D, D-x, 1), void();
        int md=(l+r)/2;
        update(l, md, 2*i, idx, x);
        update(md+1, r, 2*i+1, idx, x);
        merge(l, r, i);
        //cout<<"upd "<<d[i].ans<<' '<<d[i].cnt<<' '<<d[i].x<<' '<<d[i].y<<'\n';
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m>>D;
    for (int i=1; i<=n; i++) cin>>a[i], srt.push_back({a[i], i});
    for (int i=1; i<=m; i++) cin>>b[i], srt.push_back({b[i], i+n});
    sort(srt.begin(), srt.end());
    s.build(1, n+m ,1);
    for (int i=1; i<=n; i++)
    {
        auto idx=lower_bound(srt.begin(), srt.end(), make_pair(a[i], i))-srt.begin()+1;
        //cout<<"idx "<<idx<<'\n'; 
        s.update(1, n+m, 1, idx, a[i]);
    }
    //cout<<"ans "<<s.d[1].ans<<'\n';
    for (int i=1; i<=m; i++)
    {
        auto idx=lower_bound(srt.begin(), srt.end(), make_pair(b[i], (int)(i+n)))-srt.begin()+1;
        s.update(1, n+m, 1, idx, b[i]);
        cout<<s.d[1].ans/2;
        if (s.d[1].ans%2) cout<<".5";
        cout<<' ';
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 35 / 35
• Subtask 4: 41 / 41