結果
問題 | 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){@Overridevoid println(Object obj){ super.println(obj == null ? "null" : obj); };@Overrideprotected 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{@Overridepublic 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;}@Overridepublic String toString(){ return "(" +u.id +"," +v.id +")"; }}class Node extends Nd{Node p,hp;Node(int id){ super(id); }@Overridepublic 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) ' ');}} elseprint(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();}}