#1130809 (Java) No.674 n連勤

• 問題: No.674 n連勤
• ユーザー: 37zigen
• 提出日時: 2025-11-02 12:50:05
• 言語: Java (openjdk 23)
• 結果: AC
• 実行時間: 537 ms / 2,000 ms
• コード長: 6,759 bytes
• コンパイル時間: 3,151 ms
• コンパイル使用メモリ: 91,640 KB
• 実行使用メモリ: 56,356 KB
• 最終ジャッジ日時: 2025-11-02 12:50:20
• 合計ジャッジ時間: 9,284 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 17

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Map.Entry;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Random;
import java.util.Set;
import java.util.TreeMap;

/**
 *
 * @param <PositionType>
 * @param <X>
verified:https://yukicoder.me/submissions/1130804
 */
class IntervalMap<PositionType, X> {
    TreeMap<PositionType, X> map;

    X voidValue;

    PositionType L;// 定義域は[L, R)


    PositionType R;

    Comparator<PositionType> comparator;

    /**
     * 定義域を[l, r)として、[l, r)の値をvoidValueに初期化
     *
     * @param l
     * @param r
     * @param voidValue
     */
    public IntervalMap(PositionType l, PositionType r, X voidValue) {
        map = new TreeMap<>();// 区間の左端に対して、その区間の色を返す

        this.voidValue = voidValue;
        L = l;
        R = r;
        map.put(L, voidValue);
        map.put(R, voidValue);
    }

    // [l, r)
    public void set(PositionType l, PositionType r, X val) {
        if (compare(l, L) == (-1)) {
            l = L;
        }
        if (compare(r, R) == 1) {
            r = R;
        }
        if (compare(l, r) >= 0) {
            return;
        }
        var mr = map.floorEntry(r);
        if (mr == null) {
            throw new AssertionError();
        }
        if (!mr.getKey().equals(r)) {
            // r-1, r ∈[a, b) となる区間を [a, r) [r, b) で分割
            map.put(r, mr.getValue());
        }
        do {
            PositionType ml = map.ceilingKey(l);
            if (compare(ml, r) == (-1)) {
                map.remove(ml);
            } else {
                break;
            }
        } while (true );
        map.put(l, val);
        mergeAt(l);
        mergeAt(r);
    }

    public Interval get(PositionType pos) {
        if (compare(pos, L) == (-1)) {
            throw new AssertionError();
        }
        if (compare(pos, R) >= 0) {
            throw new AssertionError();
        }
        var l = map.floorEntry(pos);
        return new Interval(l.getKey(), map.higherKey(pos), l.getValue());
    }

    class Interval {
        public PositionType l;

        public PositionType r;

        public X x;

        public Interval(PositionType l, PositionType r, X x) {
            this.l = l;
            this.r = r;
            this.x = x;
        }

        @Override
        public String toString() {
            return (((("(l,r,x)=" + l) + ",") + r) + ",") + x;
        }
    }

    /**
     * [hoge,  pos)[pos, fuga) の二つの区間が同じ値ならマージする
     *
     * @param pos
     */
    public void mergeAt(PositionType pos) {
        var left = map.lowerEntry(pos);
        if ((left != null) && left.getValue().equals(map.get(pos))) {
            map.remove(pos);
        }
    }

    @SuppressWarnings("unchecked")
    int compare(PositionType k1, PositionType k2) {
        return comparator == null ? ((Comparable<? super PositionType>) (k1)).compareTo(k2) : comparator.compare(k1, k2);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (var es : map.entrySet()) {
            sb = sb.append(((("[l=" + es.getKey()) + ",x=") + es.getValue()) + ")");
        }
        return sb.toString();
    }
}

class FastScanner {
    private static FastScanner instance = null;

    private final InputStream in = System.in;

    private final byte[] buffer = new byte[1024];

    private int ptr = 0;

    private int buflen = 0;

    private FastScanner() {
    }

    public static FastScanner getInstance() {
        if (instance == null) {
            instance = new FastScanner();
        }
        return instance;
    }

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }
        ptr = 0;
        try {
            buflen = in.read(buffer);
        } catch (IOException e) {
            e.printStackTrace();
        }
        return buflen > 0;
    }

    private int readByte() {
        if (hasNextByte()) {
            return buffer[ptr++];
        } else {
            return -1;
        }
    }

    private boolean isPrintableChar(int c) {
        return (33 <= c) && (c <= 126);
    }

    public boolean hasNext() {
        while (hasNextByte() && (!isPrintableChar(buffer[ptr]))) {
            ptr++;
        } 
        return hasNextByte();
    }

    public long nextLong() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        while ((b >= '0') && (b <= '9')) {
            n = (n * 10) + (b - '0');
            b = readByte();
        } 
        return minus ? -n : n;
    }

    public int nextInt() {
        return ((int) (nextLong()));
    }
}

class MyPrintWriter extends PrintWriter {
    private static MyPrintWriter instance = null;

    private MyPrintWriter() {
        super(System.out);
    }

    public static MyPrintWriter getInstance() {
        if (instance == null) {
            instance = new MyPrintWriter();
        }
        return instance;
    }
}

public class Main implements Runnable {
    public static void main(String[] args) throws IOException {
        Thread.setDefaultUncaughtExceptionHandler((t, e) -> System.exit(1));
        // new Main().gen();
        // new Thread(null, new Main(), "MainThreadWithLargeStack", (1024 * 1024) * 1024).start();// 1024MBスタックを確保して実行
        // new Main().test();
        // new Main().gen();
        new Main().run();
        // MergeFilesTest.test();
    }

    void solve() {
        FastScanner sc = FastScanner.getInstance();
        MyPrintWriter pw = MyPrintWriter.getInstance();
        long D = sc.nextLong();
        int Q = sc.nextInt();
        long ans = 0;
        IntervalMap<Long, Integer> set = new IntervalMap<>(Long.MIN_VALUE, Long.MAX_VALUE, -1);
        for (int QUERY = 0; QUERY < Q; QUERY++) {
            long A = sc.nextLong();
            long B = sc.nextLong();
            set.set(A, B + 1, 1);
            var interval = set.get(A);
            ans = Math.max(ans, interval.r - interval.l);
            System.out.println(ans);
        }
    }

    public void run() {
        var sc = FastScanner.getInstance();
        var pw = MyPrintWriter.getInstance();
        solve();
        // long ans=new Solver().sole(N, x, y);
        pw.flush();
    }
}