Submission #1119967

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119967		secretwood01	Snowball (JOI21_ho_t2)	Java	100 / 100	544 ms	58932 KiB

Main

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int Q = Integer.parseInt(st.nextToken());
        SB [] Arr = new SB[N];
        long [][] Pos = new long[Q+1][2];
        st = new StringTokenizer(br.readLine());
        for (int i=0;i<N;i++) {
            Arr[i] = new SB(Long.parseLong(st.nextToken()));
        }
        long currPos = 0;
        Pos[0][0] = 0;Pos[0][1] = 0;
        long [] Winds = new long[Q];
        for (int i=1;i<=Q;i++) {
            Winds[i-1] = Long.parseLong(br.readLine());
            currPos+=Winds[i-1];
            Pos[i][0] = Math.min(Pos[i-1][0], currPos);
            Pos[i][1] = Math.max(Pos[i-1][1], currPos);
        }
        Arr[0].left = Pos[Q][0];
        Arr[N-1].right = Pos[Q][1];
        for (int i=0;i<N-1;i++) {
            if (Arr[i].pos+Pos[Q][1]>Arr[i+1].pos+Pos[Q][0]) {
                int time = bs(i, Q, Pos, Arr);
                long currLeft = Arr[i].pos+Pos[time][1]; //Left Index Position
                long currRight = Arr[i+1].pos+Pos[time][0];
                if (Winds[time]>0) {
                    currLeft=currRight;
                } else {
                    currRight = currLeft;
                }
                Arr[i].right = currLeft-Arr[i].pos;
                Arr[i+1].left = currRight-Arr[i+1].pos;
            } else {
                Arr[i].right = Pos[Q][1];
                Arr[i+1].left = Pos[Q][0];
            }
        }
        for (int i=0;i<N;i++) {
            //pw.println(Arr[i].weight);
            pw.println(Arr[i].right - Arr[i].left);
        }
        pw.close();
        br.close();
    }
    public static int bs(int ind, int Q, long [][] Pos, SB [] Arr) {
        int lo = 0;
        int hi = Q;
        while (lo < hi) {
			int mid = lo + (hi - lo + 1) / 2;
			if (f(ind, mid, Pos, Arr)) {
				lo = mid;
			} else {
				hi = mid - 1;
			}
		}
		return lo;
    }
    public static boolean f(int ind, int mid, long[][] Pos, SB[] Arr) {
        long q1 = Arr[ind].pos+Pos[mid][1];
        long q2 = Arr[ind+1].pos+Pos[mid][0];
        return q1<=q2;
    }
}
class SB {
    long pos;
    long left;
    long right;
    public SB(long pos) {
        this.pos = pos;
        left = 0;
        right = 0;
    }
}

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