Submission #270660

#	Time	Username	Problem	Language	Result	Execution time	Memory
270660		Gilgamesh	Just Long Neckties (JOI20_ho_t1)	Java	0 / 100	220 ms	16120 KiB

ho_t1

import java.util.*;
import java.io.*;

public class ho_t1 {
	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);
		}
		int suffmx[] = new int[N]; //suffmx for dif2
		int prefmx[] = new int[N];
		for(int i = 0; i < N; ++i) {
			prefmx[i] = dif1[i];
			if(i > 0) prefmx[i] = Math.max(prefmx[i - 1], prefmx[i]);
		}
		for(int i = N - 1; i >= 0; --i) {
			suffmx[i] = dif2[i];
			if(i < N - 1) suffmx[i] = Math.max(suffmx[i], suffmx[i + 1]);
		}
		for(int i = 0; i <= N; ++i) {
			if(i > 0) ans[A[i].ind] = prefmx[i - 1];
			if(i < N - 1) ans[A[i].ind] = Math.max(ans[A[i].ind], suffmx[i]);
		}
		for(int i = 0; i <= N; ++i) {
			System.out.print(ans[i] + " ");
		}
		System.out.println();
		in.close();
	}
	static class nt{
		int ind, len;
		nt(int i, int l){
			ind = i; len = l;
		}
	}
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 8
• Subtask 3: 0 / 91