Submission #1231489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231489		Tenis0206	Measures (CEOI22_measures)	C++20	100 / 100	259 ms	72660 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 4e5;

int n, m, d;
int a[nmax + 5], b[nmax + 5];

vector<pair<int,int>> l;

struct arbore_indexat_binar
{
    int aib[nmax + 5];

    int ub(int x)
    {
        return (x & (-x));
    }

    void update(int poz, int val)
    {
        for(int i=poz; i<=n+m; i+=ub(i))
        {
            aib[i] += val;
        }
    }

    int query(int poz)
    {
        int rez = 0;
        for(int i=poz; i>=1; i-=ub(i))
        {
            rez += aib[i];
        }
        return rez;
    }
} aib;

struct arbore_de_intervale
{
    struct Node
    {
        int Max, Min, rez;
        int lazy;
        bool active;
        Node()
        {
            Max = Min = rez = 0;
            lazy = 0;
            active = false;
        }
    };

    Node ai[4 * nmax + 5];

    Node Merge(Node st, Node dr)
    {
        Node rez;
        rez.lazy = 0;
        if(!st.active && !dr.active)
        {
            rez.active = false;
            rez.Max = rez.Min = rez.rez = 0;
        }
        else if(!st.active)
        {
            rez.active = true;
            rez.Max = dr.Max;
            rez.Min = dr.Min;
            rez.rez = dr.rez;
        }
        else if(!dr.active)
        {
            rez.active = true;
            rez.Max = st.Max;
            rez.Min = st.Min;
            rez.rez = st.rez;
        }
        else
        {
            rez.active = true;
            rez.Max = max(st.Max, dr.Max);
            rez.Min = min(st.Min, dr.Min);
            rez.rez = max(st.rez, dr.rez);
            rez.rez = max(rez.rez, st.Max - dr.Min);
        }
        return rez;
    }

    void propag(int nod)
    {
        if(ai[nod].lazy == 0 || ai[nod].active == false)
        {
            return;
        }
        ai[nod * 2].Min += ai[nod].lazy;
        ai[nod * 2].Max += ai[nod].lazy;
        ai[nod * 2 + 1].Min += ai[nod].lazy;
        ai[nod * 2 + 1].Max += ai[nod].lazy;
        ai[nod * 2].lazy += ai[nod].lazy;
        ai[nod * 2 + 1].lazy += ai[nod].lazy;
        ai[nod].lazy = 0;
    }

    void activate(int poz, int val, int nod, int a, int b)
    {
        if(a == b)
        {
            ai[nod].active = true;
            ai[nod].Max = ai[nod].Min = val;
            ai[nod].rez = 0;
            return;
        }
        propag(nod);
        int mij = (a + b) >> 1;
        if(poz <= mij)
        {
            activate(poz, val, nod * 2, a, mij);
        }
        else
        {
            activate(poz, val, nod * 2 + 1, mij + 1, b);
        }
        ai[nod] = Merge(ai[nod * 2], ai[nod * 2 + 1]);
    }

    void update(int ua, int ub, int val, int nod, int a, int b)
    {
        if(ua <= a && ub >= b)
        {
            if(ai[nod].active)
            {
                ai[nod].lazy += val;
                ai[nod].Min += val;
                ai[nod].Max += val;
            }
            return;
        }
        propag(nod);
        int mij = (a + b) >> 1;
        if(ua <= mij)
        {
            update(ua, ub, val, nod * 2, a, mij);
        }
        if(ub > mij)
        {
            update(ua, ub, val, nod * 2 + 1, mij + 1, b);
        }
        ai[nod] = Merge(ai[nod * 2], ai[nod * 2 + 1]);
    }
} ai;

int get_poz(pair<int,int> val)
{
    int st = 1;
    int dr = n + m;
    int poz = 0;
    while(st <= dr)
    {
        int mij = (st + dr) >> 1;
        if(l[mij - 1] <= val)
        {
            poz = mij;
            st = mij + 1;
        }
        else
        {
            dr = mij - 1;
        }
    }
    return poz;
}

void print(int val)
{
    if(val % 2 == 0)
    {
        cout<<val/2<<' ';
    }
    else
    {
        double p = 0.5 * val;
        cout<<fixed<<setprecision(1);
        cout<<p<<' ';
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
#ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
#endif // home
    cin>>n>>m>>d;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        l.push_back({a[i], i});
    }
    for(int i=1; i<=m; i++)
    {
        cin>>b[i];
        l.push_back({b[i], i + n});
    }
    sort(l.begin(), l.end());
    for(int i=1; i<=n; i++)
    {
        int poz = get_poz({a[i], i});
        int cnt = aib.query(poz);
        ai.activate(poz, a[i] - (cnt - 1) * d, 1, 1, n + m);
        ai.update(poz, n + m, -d, 1, 1, n + m);
        aib.update(poz, +1);
    }
    for(int i=1; i<=m; i++)
    {
        int poz = get_poz({b[i], i + n});
        int cnt = aib.query(poz);
        ai.activate(poz, b[i] - (cnt - 1) * d, 1, 1, n + m);
        ai.update(poz, n + m, -d, 1, 1, n + m);
        aib.update(poz, +1);
        print(ai.ai[1].rez);
    }
    return 0;
}

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