Submission #1315738

#TimeUsernameProblemLanguageResultExecution timeMemory
1315738sp2028Just Long Neckties (JOI20_ho_t1)Java
100 / 100
853 ms86104 KiB
import java.util.Scanner;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;

class Pair {
    long first;
    int second;

    Pair(long first, int second) {
        this.first = first;
        this.second = second;
    }
}

public class ho_t1 {
    public static void main(String[] args) {
        Kattio io= new Kattio();
        int N = io.nextInt();
        Pair[] A = new Pair[N + 1];
        long[] B = new long[N];

        for (int i = 0; i < N + 1; ++i) {
            long a = io.nextLong();
            A[i] = new Pair(a, i); //val index
        }
        for (int i = 0; i < N; ++i) {
            B[i] = io.nextLong();
        }
        Arrays.sort(A, Comparator.comparingLong(p -> p.first)); //sort by val
        Arrays.sort(B);
        long[] left = new long[N + 1];
        long[] right = new long[N + 1];

        for (int i = 0; i < N; ++i) {
            left[i + 1] = Math.max(left[i], Math.max(A[i].first - B[i], 0L));
            right[i + 1] = Math.max(right[i], Math.max(A[N - i].first - B[N - i - 1], 0L));
        }

        int[] res = new int[N + 1];
        for (int i = 0; i < N + 1; ++i) {
            int id = A[i].second;
            res[id] = (int)Math.max(left[i], right[N - i]); 
        }

        for (int i = 0; i < N + 1; ++i) {
           io.print(res[i] + " ");
        }
       io.println();
        io.close();
    }
    static class Kattio extends PrintWriter {
		private BufferedReader r;
		private StringTokenizer st;
		public Kattio() { this(System.in, System.out); }
		public Kattio(InputStream i, OutputStream o) {
			super(o);
			r = new BufferedReader(new InputStreamReader(i));
		}
		public String next() {
			try {
				while (st == null || !st.hasMoreTokens())
					st = new StringTokenizer(r.readLine());
				return st.nextToken();
			} catch (Exception e) { }
			return null;
		}
		public int nextInt() { return Integer.parseInt(next()); }
		public long nextLong() { return Long.parseLong(next()); }
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...