Submission #74943497

---

Source Code Expand

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

public class Main {
    static final int OFFSET = 50000;
    static final int SIZE = 100001;
    static int[] psum = new int[SIZE + 2];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] D = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) D[i] = Integer.parseInt(st.nextToken());

        if (M > 0) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                int x = Integer.parseInt(st.nextToken()) + OFFSET;
                if (x >= 0 && x < SIZE) psum[x + 1]++;
            }
        }
        for (int i = 0; i <= SIZE; i++) psum[i + 1] += psum[i];

        // Represent reachable as sorted list of disjoint intervals [lo, hi]
        // For each step d:
        //   canExec within interval [lo,hi]:
        //     if d>0: subinterval of p where no barr in [p, p+d]
        //             = p where nextBarrRight[p] > p+d
        //             blocked if nextBarrRight[p] <= p+d
        //             Find first barricade b >= lo: if b <= hi+d, then p in [b-d, hi] blocked
        //             Actually: split interval at each barricade within [lo, hi+d]
        //     Simpler: for interval [lo,hi], find all barricades in [lo, hi+d]
        //             Each barricade b blocks p in [b-d, b] (clipped to [lo,hi])
        //             The canExec sub-intervals are the gaps between blocked regions
        //   next intervals = original intervals (skip) union shifted canExec intervals (execute)
        //   Then merge overlapping intervals

        // Store intervals as int[2] sorted by lo
        List<int[]> intervals = new ArrayList<>();
        intervals.add(new int[]{OFFSET, OFFSET});

        // barricade sorted list
        TreeSet<Integer> barrSet = new TreeSet<>();
        for (int i = 0; i < SIZE; i++) {
            if (psum[i + 1] > psum[i]) barrSet.add(i);
        }

        for (int step = 0; step < N; step++) {
            int d = D[step];
            List<int[]> execIntervals = new ArrayList<>();

            for (int[] seg : intervals) {
                int lo = seg[0], hi = seg[1];
                // positions p in [lo,hi] that can execute d
                // d>0: need no barr in [p, p+d], p+d < SIZE
                // d<0: need no barr in [p+d, p], p+d >= 0
                int pLo = lo, pHi = hi;
                if (d > 0) pHi = Math.min(pHi, SIZE - 1 - d);
                else pLo = Math.max(pLo, -d);
                if (pLo > pHi) continue;

                // Find barricades that block some p in [pLo, pHi]
                // d>0: barr b in [pLo, pHi+d] blocks p in [b-d, b] ∩ [pLo,pHi]
                // d<0: barr b in [pLo+d, pHi] blocks p in [b, b-d] ∩ [pLo,pHi]
                int scanLo = d > 0 ? pLo : pLo + d;
                int scanHi = d > 0 ? pHi + d : pHi;
                NavigableSet<Integer> barrs = barrSet.subSet(scanLo, true, scanHi, true);

                int cur = pLo;
                for (int b : barrs) {
                    // blocked p range
                    int bpLo = d > 0 ? b - d : b;
                    int bpHi = d > 0 ? b : b - d;
                    bpLo = Math.max(bpLo, pLo);
                    bpHi = Math.min(bpHi, pHi);
                    if (cur < bpLo) {
                        execIntervals.add(new int[]{cur + d, bpLo - 1 + d});
                    }
                    cur = Math.max(cur, bpHi + 1);
                }
                if (cur <= pHi) {
                    execIntervals.add(new int[]{cur + d, pHi + d});
                }
            }

            // merge intervals ∪ execIntervals
            List<int[]> combined = new ArrayList<>(intervals);
            combined.addAll(execIntervals);
            combined.sort(Comparator.comparingInt(a -> a[0]));

            List<int[]> merged = new ArrayList<>();
            for (int[] seg : combined) {
                if (!merged.isEmpty() && seg[0] <= merged.get(merged.size()-1)[1] + 1) {
                    merged.get(merged.size()-1)[1] = Math.max(merged.get(merged.size()-1)[1], seg[1]);
                } else {
                    merged.add(new int[]{seg[0], seg[1]});
                }
            }
            intervals = merged;
        }

        int maxPos = intervals.get(intervals.size() - 1)[1];
        System.out.println(maxPos - OFFSET);
    }
}

Submission Info

Judge Result