Submission #792248

#	Time	Username	Problem	Language	Result	Execution time	Memory
792248		Valters07	Measures (CEOI22_measures)	C++14	35 / 100	402 ms	24216 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define en cin.close();return 0;
#define pb push_back
#define fi first//printf("%lli\n",cur);
#define se second//scanf("%lli",&n);
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 2e5+15;
const ll INF = 1e18;
struct node
{
    ll mi = INF, mx = -INF, cnt = 0, lzy = 0;
};
node segt[4*N];
int mx;
void updlzy(int pos, int siz)
{
    int lzy = segt[pos].lzy;
    if(lzy)
    {
        segt[pos].mi+=lzy;
        segt[pos].mx+=lzy;
        if(siz>1)
            segt[pos*2].lzy+=lzy,
            segt[pos*2+1].lzy+=lzy;
        segt[pos].lzy=0;
    }
}
void updnode(int pos)
{
    segt[pos].cnt=segt[pos*2].cnt+segt[pos*2+1].cnt;
    segt[pos].mi=min(segt[pos*2].mi,segt[pos*2+1].mi);
    segt[pos].mx=max(segt[pos*2].mx,segt[pos*2+1].mx);
}
void upd(int lb, int rb, ll val, int l = 0, int r = mx, int pos = 1)
{
    updlzy(pos,r-l+1);
    if(rb<l||r<lb)
        return;
    if(lb<=l&&r<=rb)
        segt[pos].lzy+=val,
        updlzy(pos,r-l+1);
    else
    {
        int mid = (l+r)/2;
        upd(lb,rb,val,l,mid,pos*2);
        upd(lb,rb,val,mid+1,r,pos*2+1);
        updnode(pos);
    }
}
void setupd(int p, ll val, int sz, int l = 0, int r = mx, int pos = 1)
{
    updlzy(pos,r-l+1);
    if(l==r)
        segt[pos].mi=segt[pos].mx=val,
        segt[pos].cnt=sz;
    else
    {
        int mid = (l+r)/2;
        if(p<=mid)
            setupd(p,val,sz,l,mid,pos*2);
        else
            setupd(p,val,sz,mid+1,r,pos*2+1);
        updnode(pos);
    }
}
node get1(int lb, int rb, int l = 0, int r = mx, int pos = 1)
{
    updlzy(pos,r-l+1);
    if(rb<l||r<lb)
        return {INF,-INF,0};
    if(lb<=l&&r<=rb)
        return segt[pos];
    int mid = (l+r)/2;
    auto t1 = get1(lb,rb,l,mid,pos*2), t2 = get1(lb,rb,mid+1,r,pos*2+1);
    return {min(t1.mi,t2.mi),max(t1.mx,t2.mx),t1.cnt+t2.cnt};
}
int main()
{
    fio
//    ifstream cin("in.in");
    int n, m, d;
    cin >> n >> m >> d;
    mx=n+m-1;
    vector<pair<int,int> > a(n+m);
    for(int i = 0;i<n+m;i++)
        cin >> a[i].fi,
        a[i].se=i;
    sort(a.begin(),a.end());
    vector<int> ord(n+m);
    for(int i = 0;i<n+m;i++)
        ord[a[i].se]=i;
    ll res = 0;
    for(int i = 0;i<n+m;i++)
    {
        int val = a[ord[i]].fi, pos = ord[i];
        ll cur = d*get1(0,pos).cnt-val;
        setupd(pos,cur,1);
        upd(pos+1,n+m-1,d);
        res=max(res,get1(pos,n+m-1).mx-get1(0,pos-1).mi);
        res=max(res,get1(pos+1,n+m-1).mx-get1(0,pos).mi);
        if(i>=n)
        {
            cout << res/2;
            if(res%2)
                cout << ".5";
            cout << " ";
        }
    }
    return 0;
}

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