Submission #270600

#	Time	Username	Problem	Language	Result	Execution time	Memory
270600		Gilgamesh	Just Long Neckties (JOI20_ho_t1)	Java	Compilation error	0 ms	0 KiB

ho_t1

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

public class Main {
	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] + " ");
		}
		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);
		}
	}
}

Compilation message (stderr)

ho_t1.java:4: error: class Main is public, should be declared in a file named Main.java
public class Main {
       ^
1 error