#include<bits/stdc++.h>
#define int long long
#define BUG(x) cerr << #x << " = " << x << endl
using namespace std;
const int N = 200005;
int t,n,a[N],b[N],st[2][4*N],diff[2][N];
vector < pair < int , int > > v;
vector < pair < int , int > > ans;
void build(int id, int l, int r, int idx) {
if (l>r) return;
if (l==r) {
st[idx][id] = diff[idx][l];
return;
}
int m = (l+r)/2;
build(id*2,l,m,idx);
build(id*2+1,m+1,r,idx);
st[idx][id] = max(st[idx][id*2],st[idx][id*2+1]);
}
int get(int id, int l, int r, int u, int v, int idx) {
if (l>v || r<u) return 0;
if (l>=u && r<=v) return st[idx][id];
int m = (l+r)/2;
return max(get(id*2,l,m,u,v,idx),get(id*2+1,m+1,r,u,v,idx));
}
void solve() {
cin >> n;
for (int i = 0; i<=n; i++) {
cin >> a[i];
v.push_back({a[i],i});
}
for (int i = 0; i<n; i++) {
cin >> b[i];
}
sort(v.begin(),v.end());
sort(a,a+n+1);
sort(b,b+n);
// for (int i = 0; i<n+1; i++) {
// cout << a[i] << " ";
// }
// cout << endl;
// for (int i = 0; i<n; i++) {
// cout << b[i] << " ";
// }
// cout << endl;
for (int i = 1; i<=n; i++) {
diff[0][i] = max(a[i-1]-b[i-1],0LL);
diff[1][i] = max(a[i]-b[i-1],0LL);
// BUG(diff[0][i]);
// BUG(diff[1][i]);
}
build(1,1,n,0);
build(1,1,n,1);
for (int i = 0; i<=n; i++) {
// BUG(v[i].second);
// BUG(v[i].first);
if (i==0) {
ans.push_back({v[i].second,get(1,1,n,1,n,1)});
// BUG(ans[i].second);
continue;
}
if (i==n) {
ans.push_back({v[i].second,get(1,1,n,1,n,0)});
// BUG(ans[i].second);
continue;
}
ans.push_back({v[i].second,max(get(1,1,n,1,v[i].second,0),get(1,1,n,v[i].second+1,n,1))});
// BUG(ans[i].second);
}
sort(ans.begin(),ans.end());
for (int i = 0; i<=n; i++) {
// BUG(ans[i].first);
cout << ans[i].second << " ";
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
