oj.uz

Submission #270657

# Submission time Handle Problem Language Result Execution time Memory
270657 2020-08-17T20:59:31 Z Gilgamesh Just Long Neckties (JOI20_ho_t1) Java 11
9 / 100
 1000 ms 36580 KB 
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);
		}
		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);
		}
	}
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 16252 KB Output is correct
2 Correct 203 ms 15612 KB Output is correct
3 Correct 214 ms 15268 KB Output is correct
4 Correct 240 ms 16008 KB Output is correct
5 Correct 209 ms 15456 KB Output is correct
6 Correct 220 ms 16240 KB Output is correct
7 Correct 211 ms 15460 KB Output is correct
8 Correct 229 ms 15968 KB Output is correct
9 Correct 209 ms 15740 KB Output is correct
10 Correct 187 ms 15372 KB Output is correct
11 Correct 215 ms 16248 KB Output is correct
12 Correct 201 ms 15644 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 16252 KB Output is correct
2 Correct 203 ms 15612 KB Output is correct
3 Correct 214 ms 15268 KB Output is correct
4 Correct 240 ms 16008 KB Output is correct
5 Correct 209 ms 15456 KB Output is correct
6 Correct 220 ms 16240 KB Output is correct
7 Correct 211 ms 15460 KB Output is correct
8 Correct 229 ms 15968 KB Output is correct
9 Correct 209 ms 15740 KB Output is correct
10 Correct 187 ms 15372 KB Output is correct
11 Correct 215 ms 16248 KB Output is correct
12 Correct 201 ms 15644 KB Output is correct
13 Correct 240 ms 16216 KB Output is correct
14 Correct 263 ms 16368 KB Output is correct
15 Correct 253 ms 16004 KB Output is correct
16 Correct 216 ms 15608 KB Output is correct
17 Correct 267 ms 16972 KB Output is correct
18 Correct 261 ms 16356 KB Output is correct
19 Correct 297 ms 16456 KB Output is correct
20 Correct 277 ms 16248 KB Output is correct
21 Correct 281 ms 16752 KB Output is correct
22 Correct 272 ms 16616 KB Output is correct
23 Correct 258 ms 16012 KB Output is correct
24 Correct 284 ms 17008 KB Output is correct
25 Correct 272 ms 16884 KB Output is correct
26 Correct 290 ms 16472 KB Output is correct
27 Correct 293 ms 16860 KB Output is correct
28 Correct 284 ms 16580 KB Output is correct
29 Correct 270 ms 16004 KB Output is correct
30 Correct 266 ms 16116 KB Output is correct
31 Correct 267 ms 16876 KB Output is correct
32 Correct 275 ms 16260 KB Output is correct

Subtask #3
0 / 91.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 16252 KB Output is correct
2 Correct 203 ms 15612 KB Output is correct
3 Correct 214 ms 15268 KB Output is correct
4 Correct 240 ms 16008 KB Output is correct
5 Correct 209 ms 15456 KB Output is correct
6 Correct 220 ms 16240 KB Output is correct
7 Correct 211 ms 15460 KB Output is correct
8 Correct 229 ms 15968 KB Output is correct
9 Correct 209 ms 15740 KB Output is correct
10 Correct 187 ms 15372 KB Output is correct
11 Correct 215 ms 16248 KB Output is correct
12 Correct 201 ms 15644 KB Output is correct
13 Correct 240 ms 16216 KB Output is correct
14 Correct 263 ms 16368 KB Output is correct
15 Correct 253 ms 16004 KB Output is correct
16 Correct 216 ms 15608 KB Output is correct
17 Correct 267 ms 16972 KB Output is correct
18 Correct 261 ms 16356 KB Output is correct
19 Correct 297 ms 16456 KB Output is correct
20 Correct 277 ms 16248 KB Output is correct
21 Correct 281 ms 16752 KB Output is correct
22 Correct 272 ms 16616 KB Output is correct
23 Correct 258 ms 16012 KB Output is correct
24 Correct 284 ms 17008 KB Output is correct
25 Correct 272 ms 16884 KB Output is correct
26 Correct 290 ms 16472 KB Output is correct
27 Correct 293 ms 16860 KB Output is correct
28 Correct 284 ms 16580 KB Output is correct
29 Correct 270 ms 16004 KB Output is correct
30 Correct 266 ms 16116 KB Output is correct
31 Correct 267 ms 16876 KB Output is correct
32 Correct 275 ms 16260 KB Output is correct
33 Execution timed out 1234 ms 36580 KB Time limit exceeded
34 Halted 0 ms 0 KB -