제출 #719621

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
719621		Rafi22	Measures (CEOI22_measures)	C++14	24 / 100	218 ms	26316 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define int long long
#define ll long long
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int N=200007,pot=1<<18;

int id[N],X[N];

int BIT[N];

void ins(int x)
{
    while(x<N)
    {
        BIT[x]++;
        x+=x&(-x);
    }
}
int que(int x)
{
    int res=0;
    while(x>0)
    {
        res+=BIT[x];
        x-=x&(-x);
    }
    return res;
}

int seg1[2*pot+7],lzy1[2*pot+7];

void push1(int v)
{
    seg1[2*v]+=lzy1[v];
    seg1[2*v+1]+=lzy1[v];
    lzy1[2*v]+=lzy1[v];
    lzy1[2*v+1]+=lzy1[v];
    lzy1[v]=0;
}
void ins1(int v,int a,int b,int l,int r,int x)
{
    if(a<=l&&b>=r)
    {
        seg1[v]+=x;
        lzy1[v]+=x;
        return ;
    }
    if(r<a||l>b) return;
    push1(v);
    ins1(2*v,a,b,l,(l+r)/2,x);
    ins1(2*v+1,a,b,(l+r)/2+1,r,x);
    seg1[v]=max(seg1[2*v],seg1[2*v+1]);
}

int seg2[2*pot+7],lzy2[2*pot+7];

void push2(int v)
{
    seg2[2*v]+=lzy2[v];
    seg2[2*v+1]+=lzy2[v];
    lzy2[2*v]+=lzy2[v];
    lzy2[2*v+1]+=lzy2[v];
    lzy2[v]=0;
}
void ins2(int v,int a,int b,int l,int r,int x)
{
    if(a<=l&&b>=r)
    {
        seg2[v]+=x;
        lzy2[v]+=x;
        return ;
    }
    if(r<a||l>b) return;
    push2(v);
    ins2(2*v,a,b,l,(l+r)/2,x);
    ins2(2*v+1,a,b,(l+r)/2+1,r,x);
    seg2[v]=min(seg2[2*v],seg2[2*v+1]);
}


signed main()
{
    int n,m,d;
    cin>>n>>m>>d;
    d*=2;
    vector<int>a(n);
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        a[i]*=2;
    }
    for(int i=0;i<m;i++)
    {
        cin>>X[i];
        X[i]*=2;
    }
    if(n>0)
    {
        for(int i=0; i<m; i++)
        {
            a.pb(X[i]);
            sort(all(a));
            int l=a[0],k=0;
            for(int j=1; j<n+i+1; j++)
            {
                if(l+d>a[j]+k)
                {
                    int m=(l+d-a[j]-k)/2;
                    k+=m;
                    l+=d-m;
                }
                else l=max(a[j]-k,l+d);
            }
            if(k%2==1) cout<<k/2<<".5"<<" ";
            else cout<<k/2<<" ";
        }
    }
    else
    {
        vector<pair<int,int>>V;
        for(int i=0;i<m;i++) V.pb({X[i],i});
        sort(all(V));
        for(int i=0;i<m;i++) id[V[i].nd]=i+1;
        for(int i=0;i<2*pot;i++)
        {
            seg1[i]=-infl;
            seg2[i]=infl;
        }
        for(int i=0;i<m;i++)
        {
            ins1(1,id[i]+1,n,1,pot,-d);
            ins2(1,id[i]+1,n,1,pot,-d);
            int k=que(id[i]);
            ins(id[i]);
            ins1(1,id[i],id[i],1,pot,infl+k*d+X[i]-(k+1)*d);
            ins2(1,id[i],id[i],1,pot,-infl+k*d+X[i]-(k+1)*d);
            int x=seg1[1]-seg2[1];
            if(x%2==1) cout<<x/2<<".5 ";
            else cout<<x/2<<" ";
        }
    }


    return 0;
}

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