import java.util.*;
import java.io.*;
class Solution {
final static int MOD = 1000000007;
final static int intMax = 1000000000;
final static int intMin = -1000000000;
final static int[] dx = { 0, 0, -1, 1 };
final static int[] dy = { -1, 1, 0, 0 };
static int T;
static class Reader {
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;
public Reader() {
din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public Reader(String file_name) throws IOException {
din = new DataInputStream(new FileInputStream(file_name));
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public String readLine() throws IOException {
byte[] buf = new byte[360]; // line length
int cnt = 0, c;
while ((c = read()) != -1) {
if (c == '\n')
break;
buf[cnt++] = (byte) c;
}
return new String(buf, 0, cnt);
}
public int nextInt() throws IOException {
int ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public long nextLong() throws IOException {
long ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public double nextDouble() throws IOException {
double ret = 0, div = 1;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (c == '.') {
while ((c = read()) >= '0' && c <= '9') {
ret += (c - '0') / (div *= 10);
}
}
if (neg)
return -ret;
return ret;
}
private void fillBuffer() throws IOException {
bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
if (bytesRead == -1)
buffer[0] = -1;
}
private byte read() throws IOException {
if (bufferPointer == bytesRead)
fillBuffer();
return buffer[bufferPointer++];
}
public void close() throws IOException {
if (din == null)
return;
din.close();
}
}
public static void main(String[] args) throws Exception {
Reader in = new Reader();
int N = in.nextInt();
nt[] A = new nt[N + 1];
int[] B = new int[N];
for(int i = 0; i <= N; ++i) {
int len = in.nextInt();
A[i] = new nt(i, len);
}
for(int i = 0; i < N; ++i) {
B[i] = in.nextInt();
}
Arrays.sort(A, (a, b) -> a.len - b.len);
Arrays.sort(B);
int[] ans = new int[N + 1];
int[] dif1 = new int[N];
int[] dif2 = new int[N];
for(int i = 0; i < N; ++i) {
dif1[i] = Math.max(A[i].len - B[i], 0);
dif2[i] = Math.max(A[i + 1].len - B[i], 0);
}
MaxSegTree mst1 = new MaxSegTree(N, dif1);
MaxSegTree mst2 = new MaxSegTree(N, dif2); //all to the right
for(int i = 0; i <= N; ++i) {
if(i == 0) {
ans[A[i].ind] = mst2.getMax(0, N - 1);
}
else if(i == N) {
ans[A[i].ind] = mst1.getMax(0, N - 1);
}
else {
ans[A[i].ind] = Math.max(mst1.getMax(0, i - 1), mst2.getMax(i, N - 1));
}
}
for(int i = 0; i <= N; ++i) {
System.out.print(ans[i]);
if(i < N) System.out.print(" ");
}
System.out.println();
in.close();
}
static class nt{
int ind, len;
nt(int i, int l){
ind = i; len = l;
}
}
static class MaxSegTree{
int[] MT; // tree of maxes
int N; // length of A
int[] W; // array of spiciness
MaxSegTree(int n, int[] w){
N = n; W = w;
MT = new int[4*N-1];
buildMax();
}
// build the whole segment tree [ O(n) ]
void buildMax() {
buildMax(0, 0, N-1);
}
//builds spiciness segtree where parent is max of children
void buildMax(int node, int start, int end) {
if( start==end ) {
MT[node] = W[start];
}
else {
int mid = (start + end)/2;
buildMax(2*node+1, start, mid); // build left child
buildMax(2*node+2, mid+1, end); // build right child
MT[node] = Math.max(MT[2*node+1],MT[2*node+2]);
}
}
// add "val" to A[loc]
void add(int node, int start, int end, int loc, int val) {
if( start==end ) { // leaf node
W[loc] += val;
MT[node] += val;
}
else {
int mid = (start+end)/2;
if( start<=loc && loc<=mid ) { // loc is in the left child
add(2*node+1, start, mid, loc, val);
}
else { // loc is in the right child
add(2*node+2, mid+1, end, loc, val);
}
MT[node] = Math.max(MT[2*node+1],MT[2*node+2]);
}
}
// add "val" to A[loc]
void add(int loc, int val) {
add(0, 0, N-1, loc, val);
}
//find the max of W[low] to W[high]
int getMax(int node, int start, int end, int low, int high) {
// range represented by node is all outside of [low, high]
if( high < start || end < low )
return 0;
// range represented by node is all inside [low, high]
if( low <= start && end <= high )
return MT[node];
// there is overlap between [start, end] and [low, high]
int mid = (start+end)/2;
int s1 = getMax(2*node+1, start, mid, low, high);
int s2 = getMax(2*node+2, mid+1, end, low, high);
return Math.max(s1, s2);
}
//find the max of W[low][1] to W[high][1]
int getMax(int low, int high) {
return getMax(0, 0, N-1, low, high);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
89 ms |
10360 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
89 ms |
10360 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
89 ms |
10360 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
