Submission #984184

#	Time	Username	Problem	Language	Result	Execution time	Memory
984184		alexdd	Measures (CEOI22_measures)	C++17	100 / 100	397 ms	50420 KiB

Main

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
#define int long long
const int INF = 1e18;
int n,m,d;
int a[200055];
struct node
{
    int bestle,bestri;
    int rez;
    int cnt;
};
node combine(node x, node y)
{
    if(x.cnt==0)
        return y;
    if(y.cnt==0)
        return x;
    node aux;
    aux.rez = max(max(x.rez,y.rez), x.bestle + y.bestri);
    aux.cnt = x.cnt + y.cnt;
    aux.bestle = max(y.bestle, x.bestle + d*y.cnt);
    aux.bestri = max(x.bestri, y.bestri + d*x.cnt);
    return aux;
}
///max((a[i] - d*i) + (-a[j]+d*j))
node get_node(int val, int cate)
{
    node aux;
    aux.cnt = cate;
    aux.rez = d*(cate-1);
    aux.bestle = val + d*(cate-1);
    aux.bestri = -val + d*cate;
    return aux;
}
node aint[530000];
void upd(int nod, int st, int dr, int poz, node newv)
{
    if(st==dr)
    {
        aint[nod]=newv;
        return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij) upd(nod*2,st,mij,poz,newv);
    else upd(nod*2+1,mij+1,dr,poz,newv);
    aint[nod] = combine(aint[nod*2], aint[nod*2+1]);
}
map<int,int> mp,nrm;
int cntnrm;
int fr[200055];
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>d;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        mp[a[i]]++;
    }
    for(int pas=1;pas<=m;pas++)
    {
        cin>>a[n+pas];
        mp[a[n+pas]]++;
    }
    for(auto it:mp)
        nrm[it.first]=++cntnrm;
    for(int i=1;i<=n;i++)
    {
        fr[nrm[a[i]]]++;
        upd(1,1,cntnrm,nrm[a[i]],get_node(a[i],fr[nrm[a[i]]]));
    }
    for(int i=n+1;i<=n+m;i++)
    {
        fr[nrm[a[i]]]++;
        upd(1,1,cntnrm,nrm[a[i]],get_node(a[i],fr[nrm[a[i]]]));

        int mxm = max(0LL,aint[1].rez);
        if(mxm%2==0) cout<<mxm/2<<" ";
        else cout<<mxm/2<<".5 ";
    }
    return 0;
}

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