#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;
}
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;
}
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
Compilation message
Main.cpp: In function 'long long int propag(long long int)':
Main.cpp:20:1: warning: no return statement in function returning non-void [-Wreturn-type]
20 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
488 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
488 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
495 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
495 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
