| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1043967 |
2024-08-05T05:21:09 Z |
ㅇㅇ(#11061) |
Measures (CEOI22_measures) |
C++17 |
|
48 ms |
20308 KB |
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using ll=long long;
const int N=222222;
int n,m,k,c[N],cnt[N];
ll d,a[N],b[N];
struct Seg{
struct node{
ll cnt=0,mn=0,mx=0,res=0;
}T[2*N];
node mrg(node L,node R){
if(!L.cnt) return R;
if(!R.cnt) return L;
node ret;
ret.cnt=L.cnt+R.cnt;
ret.mn=min(L.mn,R.mn+L.cnt*d);
ret.mx=max(L.mx,R.mx+L.cnt*d);
ret.res=max({L.mx,R.mx,R.mx+L.cnt*d-L.mn});
return ret;
}
void upd(int nd,int l,int r,int x){
if(l==r){
T[nd].cnt=1;
T[nd].mn=T[nd].mx=d-c[x];
return;
}
int m=(l+r)>>1,ln=nd+1,rn=nd+2*(m-l+1);
if(x<=m) upd(ln,l,m,x);
else upd(rn,m+1,r,x);
T[nd]=mrg(T[ln],T[rn]);
}
}T;
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>m>>d;
for(int i=1;i<=n;i++){
cin>>a[i];
c[i]=a[i];
}
for(int i=1;i<=m;i++){
cin>>b[i];
c[i+n]=b[i];
}
sort(c+1,c+n+m+1);
k=unique(c+1,c+n+m+1)-c-1;
for(int i=1;i<=n;i++){
a[i]=lower_bound(c+1,c+k+1,a[i])-c;
cnt[a[i]]++;
}
for(int i=1;i<=m;i++){
b[i]=lower_bound(c+1,c+k+1,b[i])-c;
cnt[b[i]]++;
}
for(int i=2;i<=k;i++) cnt[i]+=cnt[i-1];
for(int i=1;i<=n;i++) a[i]=cnt[a[i]]--;
for(int i=1;i<=m;i++) b[i]=cnt[b[i]]--;
for(int i=1;i<=n;i++) T.upd(1,1,n+m,a[i]);
for(int i=1;i<=m;i++){
T.upd(1,1,n+m,b[i]);
ll ans=T.T[1].res;
if(ans%2==0) cout<<ans/2<<" ";
else cout<<ans/2<<".5 ";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
20308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
20308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
