Submission #992079

#	Time	Username	Problem	Language	Result	Execution time	Memory
992079		Savu_Stefan_Catalin	Measures (CEOI22_measures)	C++14	0 / 100	598 ms	524288 KiB

Main

#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int NMAX=2e5+505;
int ar1[4*NMAX+505],ar2[4*NMAX+505],ar[4*NMAX+505],lazy[4*NMAX+505];
int n,m,d,N,ind[NMAX+505],a[NMAX+505];
void upd(int nod,int val)
{
    ar1[nod]+=val;
    ar2[nod]+=val;
    lazy[nod]+=val;
}
int propag(int nod)
{
    upd(nod*2,lazy[nod]);
    upd(nod*2+1,lazy[nod]);
    lazy[nod]=0;
}
void updatelazy(int st,int dr,int nod,int qa,int qb,int val)
{
    if (qa<=st&&dr<=qb)
    {
        upd(nod,val);
        return ;
    }
    propag(nod);
    int mij=(st+dr)/2;
    if (qa<=mij) updatelazy(st,mij,nod*2,qa,qb,val);
    if (qb>mij) updatelazy(mij+1,dr,nod*2+1,qa,qb,val);
    ar1[nod]=max(ar1[nod*2],ar1[nod*2+1]);
    ar2[nod]=min(ar2[nod*2],ar2[nod*2+1]);
}
void update(int st,int dr,int nod,int poz,int val)
{
    if (st!=dr) propag(nod);
    if (st==dr)
    {
        ar1[nod]=ar2[nod]=val;
        ar[nod]=1;
        return ;
    }
    int mij=(st+dr)/2;
    if (poz<=mij) update(st,mij,nod*2,poz,val);
    else update(mij+1,dr,nod*2+1,poz,val);
    ar1[nod]=max(ar1[nod*2],ar1[nod*2+1]);
    ar2[nod]=min(ar2[nod*2],ar2[nod*2+1]);
    ar[nod]=ar[nod*2]+ar[nod*2+1];
}
int query1(int st,int dr,int nod,int qa,int qb)
{
    if (qa<=st&&dr<=qb)
    {
        return ar[nod];
    }
    int mij=(st+dr)/2,ras1=0,ras2=0;
    if (qa<=mij) ras1=query1(st,mij,nod*2,qa,qb);
    if (qb>mij) ras2=query1(mij+1,dr,nod*2+1,qa,qb);
    return ras1+ras2;
}
void add(int i)
{
    int poz=ind[i];
    updatelazy(1,N,1,poz+1,N,d);
    update(1,N,1,poz,(query1(1,N,1,1,poz)+1)*d-a[i]);
}
int cmp(int x,int y)
{
    return a[x]<a[y];
}
void updbeg(int st,int dr,int nod)
{
    ar1[nod]=-1e17;
    ar2[nod]=1e17;
    if (st==dr) return ;
    int mij=(st+dr)/2;
    updbeg(st,mij,nod*2);
    updbeg(mij+1,dr,nod*2+1);
}
signed main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>d;
    for (int i=1;i<=n;++i)
    {
        cin>>a[i];
    }
    for (int j=1;j<=m;++j)
    {
        cin>>a[j+n];
    }
    N=n+m;
    updbeg(1,N,1);
    for (int i=1;i<=N;++i)
    {
        ind[i]=i;
    }
    sort(ind+1,ind+N+1,cmp);
    for (int i=1;i<=n;++i)
    {
        add(i);
    }
    for (int j=1;j<=m;++j)
    {
        int i=j+n;
        add(i);
        cout<<(ar1[1]-ar2[1])/2;
        if ((ar1[1]-ar2[1])%2) {cout<<".5";}
        cout<<" ";
    }
    return 0;
}
/// 1/2*max(d*(j-i)-(a[j]-a[i]))=1/2*max((d*j-a[j])-(d*i-a[i]))=1/2(max(d*i-a[i])-min(d*i-a[i]))

Compilation message (stderr)

Main.cpp: In function 'long long int propag(long long int)':
Main.cpp:19:1: warning: no return statement in function returning non-void [-Wreturn-type]
   19 | }
      | ^

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