제출 #992096

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
992096		Savu_Stefan_Catalin	Measures (CEOI22_measures)	C++14	100 / 100	233 ms	32288 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,a[NMAX+505],ras,ind[NMAX+505];
pair<int,int> indd[NMAX+505];
void upd(int nod,int val)
{
    ar1[nod]+=val;
    ar2[nod]+=val;
    lazy[nod]+=val;
}
void 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;
}
int querymax(int st,int dr,int nod,int qa,int qb)
{
    if (qa<=st&&dr<=qb)
    {
        return ar1[nod];
    }
    propag(nod);
    int mij=(st+dr)/2,ras1=-1e17,ras2=-1e17;
    if (qa<=mij) ras1=querymax(st,mij,nod*2,qa,qb);
    if (qb>mij) ras2=querymax(mij+1,dr,nod*2+1,qa,qb);
    return max(ras1,ras2);
}
int querymin(int st,int dr,int nod,int qa,int qb)
{
    if (qa<=st&&dr<=qb)
    {
        return ar2[nod];
    }
    propag(nod);
    int mij=(st+dr)/2,ras1=1e17,ras2=1e17;
    if (qa<=mij) ras1=querymin(st,mij,nod*2,qa,qb);
    if (qb>mij) ras2=querymin(mij+1,dr,nod*2+1,qa,qb);
    return min(ras1,ras2);
}
void add(int i)
{
    int poz=ind[i];
    updatelazy(1,N,1,poz,N,d);
    update(1,N,1,poz,(query1(1,N,1,1,poz)+1)*d-a[i]);
    ras=max(ras,querymax(1,N,1,poz,N)-querymin(1,N,1,1,poz));
}
void updbeg(int st,int dr,int nod)
{
    ar1[nod]=-1e10;
    ar2[nod]=1e10;
    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)
    {
        indd[i].first=a[i];
        indd[i].second=i;
    }
    sort(indd+1,indd+N+1);
    for (int i=1;i<=N;++i)
    {
        ind[indd[i].second]=i;
    }
    for (int i=1;i<=n;++i)
    {
        add(i);
    }
    for (int j=1;j<=m;++j)
    {
        int i=j+n;
        add(i);
        cout<<ras/2;
        if ((ras)%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]))
/// 2 3 1 -> 3 1 2 -> 2 3 1

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