Submission #1270589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270589		vampirr	Snowball (JOI21_ho_t2)	Java	100 / 100	1440 ms	194524 KiB

Main

import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		int Q = in.nextInt();
		long[] locs = new long[N];
		long[] W = new long[Q];
		long[] P = new long[Q+1];
		long[] R = new long[Q+1];
		long[] L = new long[Q+1];
		
		for (int i=0; i<N; i++) {
			locs[i]=in.nextLong();
		}
		
		R[0]=0; W[0]=0; L[0]=0;
		for (int i=0; i<Q; i++) {
			W[i]=in.nextLong();
			P[i+1]=P[i]+W[i];
		}
		
		for (int i=1; i<=Q; i++) {
			L[i]=Math.min(L[i-1], P[i]);
			R[i]=Math.max(R[i-1], P[i]);
		}
		
		long[] leftbounds = new long[N];
		long[] rightbounds = new long[N];
		for (int i=0; i<N; i++) {
			leftbounds[i]=locs[i]+L[Q];
			rightbounds[i]=locs[i]+R[Q];
		}
		
		for (int i=0; i<N-1; i++) {
			long gap = locs[i+1]-locs[i];
			int t = findt(Q,R,L,gap);
			
			long meet;
			if (t>=1 && W[t-1]>=0) {
				meet = locs[i+1]+L[t];
			}else {
				meet = locs[i]+R[t];
			}
			
			rightbounds[i] = Math.min(rightbounds[i], meet);
			leftbounds[i+1] = Math.max(leftbounds[i+1], meet);
		}
		
		for (int i=1; i<N; i++){
	        leftbounds[i] = Math.max(leftbounds[i], leftbounds[i-1]);
	    }
	    for (int i=N-2; i>=0; i--){
	        rightbounds[i] = Math.min(rightbounds[i], rightbounds[i+1]);
	    }
	    for (int i=0; i<N; i++) {
	    	long ans = rightbounds[i]-leftbounds[i];
	    	System.out.println(Math.min(ans, R[Q]-L[Q]));
	    }
	    in.close();
		
	}
	
	public static int findt(int Q, long[] R, long[] L, long gap) {
		int lo=1; int hi=Q; int ans=Q; 
		while (lo<=hi) {
			int mid = (lo+hi)/2;
			if (R[mid]-L[mid] >= gap) {
				ans=mid;
				hi=mid-1;
			} else {
				lo=mid+1;
			}
		}
		return ans;
	}

}

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67