// #cheat_when_I_was_young
// #cheatkhitacontre #khionhatoicheat
// #thaycuckythatvong
#include "bits/stdc++.h"
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
const int NM = 2e5 + 5;
int n, a[NM], b[NM], tmp1[NM], tmp2[NM], tree1[NM<<2], tree2[NM<<2], ans[NM];
pair<int,int> c[NM];
void build(int *tree, int *arr, int id = 1, int l = 1, int r = n) {
if (l == r) {
tree[id] = arr[l];
return;
}
int mid = (l+r) >> 1;
build(tree, arr, id<<1, l, mid);
build(tree, arr, id<<1|1, mid+1, r);
tree[id] = max(tree[id<<1], tree[id<<1|1]);
}
int get(int *tree, int u, int v, int id = 1, int l = 1, int r = n) {
if (v < l || r < u) return 0;
if (u <= l && r <= v) return tree[id];
int mid = (l+r) >> 1;
return max(get(tree, u, v, id<<1, l, mid), get(tree, u, v, id<<1|1, mid+1, r));
}
signed main() {
IOS;
cin >> n;
for (int i = 1; i <= n+1; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) cin >> b[i];
for (int i = 1; i <= n+1; ++i) c[i] = {a[i], i};
sort(a+1, a+n+2);
sort(b+1, b+n+1);
sort(c+1, c+n+2);
for (int i = 1; i <= n; ++i) {
tmp1[i] = max(a[i] - b[i], 0);
tmp2[i] = max(a[i+1] - b[i], 0);
}
build(tree1, tmp1);
build(tree2, tmp2);
for (int i = 1; i <= n+1; ++i) {
int x = c[i].second;
if (x == 1) ans[x] = get(tree2, 1, n);
else if (x == n+1) ans[x] = get(tree1, 1, n);
else ans[x] = max(get(tree1, 1, x-1), get(tree2, x, n));
}
for (int i = 1; i <= n+1; ++i) cout << ans[i] << " \n"[i == n+1];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
