#932050 (Java) No.674 n連勤

• 問題: No.674 n連勤
• ユーザー: ゆうき
• 提出日時: 2023-11-27 08:51:15
• 言語: Java (openjdk 23)
• 結果: AC
• 実行時間: 244 ms / 2,000 ms
• コード長: 10,079 bytes
• コンパイル時間: 3,649 ms
• コンパイル使用メモリ: 96,740 KB
• 実行使用メモリ: 46,144 KB
• 最終ジャッジ日時: 2024-09-26 12:11:57
• 合計ジャッジ時間: 7,255 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

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

ソースコード

import static java.lang.Math.*;
import static java.util.Arrays.*;

import java.io.*;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.ThreadLocalRandom;
import java.util.function.*;
import java.util.stream.IntStream;

class Solver{
  long st = System.currentTimeMillis();

  long elapsed(){ return System.currentTimeMillis() -st; }

  void reset(){ st = System.currentTimeMillis(); }

  static int infI = (1 <<30) -1;
  static long infL = 1L <<60;
  //   static long mod = (int) 1e9 +7;
  static long mod = 998244353;
  static String yes = "Yes";
  static String no = "No";

  static Random rd = ThreadLocalRandom.current();
  MyReader in = new MyReader(System.in);
  MyWriter out = new MyWriter(System.out);
  MyWriter log = new MyWriter(System.err){
    @Override
    void println(Object obj){ super.println(obj == null ? "null" : obj); };

    @Override
    protected void ln(){
      super.ln();
      flush();
    };
  };

  Object solve(){
    long D = in.lg();
    int Q = in.it();
    var set = new RangeSet();
    long max = 0;
    while (Q-- > 0) {
      long l = in.lg();
      long r = in.lg() +1;
      set.add(l,r);
      long[] t = set.get(l);
      max = max(max,t[1] -t[0]);
      out.println(max);
    }
    return null;
  }
}

class RangeSet{
  @Override
  public String toString(){
    List<String> list = new ArrayList<>();
    for (var s:set)
      list.add(Arrays.toString(s));

    return list.toString();
  }

  TreeSet<long[]> set;

  public RangeSet(){
    set = new TreeSet<>(Comparator.comparing(t -> t[0]));
    long infL = Solver.infL;
    set.add(new long[]{-infL, -infL});
    set.add(new long[]{infL, infL});
  }

  void add(long l,long r){
    long[] t = {l, r};
    for (var s = set.floor(t);t[0] <= s[1];s = set.floor(t))
      adj(t,s);
    for (var s = set.ceiling(t);s[0] <= t[1];s = set.ceiling(t))
      adj(t,s);
    set.add(t);
  }

  void adj(long[] t,long[] s){
    set.remove(s);
    t[0] = min(t[0],s[0]);
    t[1] = max(t[1],s[1]);
  }

  public long[] get(long l){ return set.floor(new long[]{l}); }
}

abstract class Dijkstra<E, L extends Comparable<L>> extends Graph<E>{
  private L[] len;
  private int[] arr;
  private int[] rev;
  private int size;
  private Edge<E>[] pre;

  @SuppressWarnings("unchecked")
  public Dijkstra(int n,boolean dir){
    super(n,dir);
    len = (L[]) new Comparable[n];
    arr = new int[n];
    rev = new int[n];
  }

  protected abstract L zero();

  protected abstract L inf();

  protected abstract L f(L l,E val);

  @SuppressWarnings("unchecked")
  public void calcFrom(int s){
    init();
    pre = new Edge[n];
    set(s,zero());
    while (!isEmpty()) {
      var cur = poll();
      L l = len[cur];

      for (var e:go(cur)) {
        L ll = f(l,e.val);
        if (ll.compareTo(len[e.v.id]) < 0) {
          pre[e.v.id] = e;
          set(e.v.id,ll);
        }
      }
    }
  }

  public L len(int t){ return len[t]; }

  public Deque<Edge<E>> path(int t){
    Deque<Edge<E>> ret = new ArrayDeque<>();
    while (pre[t] != null) {
      ret.addFirst(pre[t]);
      t = pre[t].u.id;
    }

    return ret;
  }

  private void init(){
    setAll(len,i -> inf());
    setAll(arr,i -> i);
    setAll(rev,i -> i);
    size = n;
  }

  private boolean isEmpty(){ return size == 0; }

  private void set(int i,L l){
    if (size <= rev[i] || len[i].compareTo(l) <= 0)
      return;
    len[i] = l;
    heapfy(rev[i]);
  }

  private int poll(){
    int ret = arr[0];
    heapfy(swap(0,--size));
    return ret;
  }

  private void heapfy(int k){
    int p = k -1 >>1;
    if (0 <= p && len[arr[p]].compareTo(len[arr[k]]) > 0) {
      heapfy(swap(p,k));
      return;
    }

    int c = k <<1 |1;
    if (size <= c)
      return;

    if (c +1 < size && len[arr[c +1]].compareTo(len[arr[c]]) < 0)
      c++;

    if (len[arr[c]].compareTo(len[arr[k]]) < 0)
      heapfy(swap(c,k));
  }

  private int swap(int i,int j){
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
    rev[arr[i]] = i;
    rev[arr[j]] = j;
    return i;
  }
}

class Edge<L> extends Nd{
  Node u,v;
  L val;

  Edge(int id,Node u,Node v,L val){
    super(id);
    this.u = u;
    this.v = v;
    this.val = val;
  }

  @Override
  public String toString(){ return "(" +u.id +"," +v.id +")"; }
}

class Node extends Nd{
  Node p,hp;

  Node(int id){ super(id); }

  @Override
  public String toString(){ return "" +id; }
}

class Nd{
  int id,l,r;

  Nd(int id){ this.id = id; }
}

class Graph<L> {
  public int n;
  List<Edge<L>> es;
  Node[] nds;
  private List<List<Edge<L>>> go,back;

  public Graph(int n,boolean dir){
    this.n = n;
    nds = new Node[n];
    go = new ArrayList<>();
    back = dir ? new ArrayList<>() : go;
    for (int i = 0;i < n;i++) {
      nds[i] = new Node(i);
      go.add(new ArrayList<>());
      back.add(new ArrayList<>());
    }
    es = new ArrayList<>();
  }

  public void addEdge(int u,int v){ addEdge(u,v,null); }

  public void addEdge(int u,int v,L l){
    Edge<L> e = new Edge<>(es.size(),nds[u],nds[v],l);
    es.add(e);
    go.get(u).add(e);
    back.get(v).add(new Edge<>(e.id,e.v,e.u,e.val));
  }

  public List<Edge<L>> go(int ui){ return go.get(ui); }

  public List<Edge<L>> back(int ui){ return back.get(ui); }
}

class Util{
  static char[] arrC(int N,IntUnaryOperator f){
    char[] ret = new char[N];
    for (int i = 0;i < N;i++)
      ret[i] = (char) f.applyAsInt(i);
    return ret;
  }

  static int[] arrI(int N,IntUnaryOperator f){
    int[] ret = new int[N];
    setAll(ret,f);
    return ret;
  }

  static long[] arrL(int N,IntToLongFunction f){
    long[] ret = new long[N];
    setAll(ret,f);
    return ret;
  }

  static double[] arrD(int N,IntToDoubleFunction f){
    double[] ret = new double[N];
    setAll(ret,f);
    return ret;
  }

  static <T> T[] arr(T[] arr,IntFunction<T> f){
    setAll(arr,f);
    return arr;
  }

}

class MyReader{
  private byte[] buf = new byte[1 <<16];
  private int ptr = 0;
  private int tail = 0;
  private InputStream in;

  MyReader(InputStream in){ this.in = in; }

  private byte read(){
    if (ptr == tail)
      try {
        tail = in.read(buf);
        ptr = 0;
      } catch (IOException e) {}
    return buf[ptr++];
  }

  private boolean isPrintable(byte c){ return 32 < c && c < 127; }

  private byte nextPrintable(){
    byte ret = read();
    while (!isPrintable(ret))
      ret = read();
    return ret;
  }

  int it(){ return toIntExact(lg()); }

  int[] it(int N){ return Util.arrI(N,i -> it()); }

  int[][] it(int H,int W){ return Util.arr(new int[H][],i -> it(W)); }

  int idx(){ return it() -1; }

  int[] idx(int N){ return Util.arrI(N,i -> idx()); }

  int[][] idx(int H,int W){ return Util.arr(new int[H][],i -> idx(W)); }

  long lg(){
    byte i = nextPrintable();
    boolean negative = i == 45;
    long n = negative ? 0 : i -'0';
    while (isPrintable(i = read()))
      n = 10 *n +i -'0';
    return negative ? -n : n;
  }

  long[] lg(int N){ return Util.arrL(N,i -> lg()); }

  long[][] lg(int H,int W){ return Util.arr(new long[H][],i -> lg(W)); }

  double dbl(){ return Double.parseDouble(str()); }

  double[] dbl(int N){ return Util.arrD(N,i -> dbl()); }

  double[][] dbl(int H,int W){ return Util.arr(new double[H][],i -> dbl(W)); }

  char[] ch(){ return str().toCharArray(); }

  char[][] ch(int H){ return Util.arr(new char[H][],i -> ch()); }

  String line(){
    StringBuilder sb = new StringBuilder();

    for (byte c;(c = read()) != '\n';)
      sb.append((char) c);
    return sb.toString();
  }

  String str(){
    StringBuilder sb = new StringBuilder();
    sb.append((char) nextPrintable());

    for (byte c;isPrintable(c = read());)
      sb.append((char) c);
    return sb.toString();
  }

  String[] str(int N){ return Util.arr(new String[N],i -> str()); }

}

class MyWriter{
  OutputStream out;
  byte[] buf = new byte[1 <<16];
  byte[] ibuf = new byte[20];
  int tail = 0;

  MyWriter(OutputStream out){ this.out = out; }

  void flush(){
    try {
      out.write(buf,0,tail);
      tail = 0;
    } catch (IOException e) {
      e.printStackTrace();
    }
  }

  protected void ln(){ write((byte) '\n'); }

  private void write(byte b){
    buf[tail++] = b;
    if (tail == buf.length)
      flush();
  }

  private void write(byte[] b,int off,int len){
    for (int i = off;i < off +len;i++)
      write(b[i]);
  }

  private void write(long n){
    if (n < 0) {
      n = -n;
      write((byte) '-');
    }

    int i = ibuf.length;
    do {
      ibuf[--i] = (byte) (n %10 +'0');
      n /= 10;
    } while (n > 0);

    write(ibuf,i,ibuf.length -i);
  }

  private void print(Object obj){
    if (obj instanceof Boolean)
      print((boolean) obj ? Solver.yes : Solver.no);
    else if (obj instanceof Integer)
      write((int) obj);
    else if (obj instanceof Long)
      write((long) obj);
    else if (obj instanceof char[] cs)
      for (char b:cs)
        write((byte) b);
    else if (obj.getClass().isArray()) {
      int l = Array.getLength(obj);
      for (int i = 0;i < l;i++) {
        print(Array.get(obj,i));
        if (i +1 < l)
          write((byte) ' ');
      }
    } else
      print(Objects.toString(obj).toCharArray());
  }

  void println(Object obj){
    if (obj == null)
      return;

    if (obj instanceof Collection<?> co)
      for (Object e:co)
        println(e);
    else if (obj.getClass().isArray() && Array.getLength(obj) > 0 && Array.get(obj,0).getClass().isArray()) {
      int l = Array.getLength(obj);
      for (int i = 0;i < l;i++)
        println(Array.get(obj,i));
    } else {
      print(obj);
      ln();
    }
  }

  void printlns(Object... o){
    print(o);
    ln();
  }
}

class Main{
  public static void main(String[] args) throws Exception{
    new Solver(){
      public void exe(){
        out.println(solve());
        //        Optional.ofNullable(solve()).ifPresent(System.out::println);
        out.flush();
        log.println(elapsed());
      }
    }.exe();
  }
}