This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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),
updlzy(pos*2+1,r-mid);
else
setupd(p,val,sz,mid+1,r,pos*2+1),
updlzy(pos*2,mid-l+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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |