結果
問題 |
No.3297 Bake Cookies
|
ユーザー |
|
提出日時 | 2025-10-05 13:57:31 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 340 ms / 2,000 ms |
コード長 | 21,117 bytes |
コンパイル時間 | 3,804 ms |
コンパイル使用メモリ | 103,476 KB |
実行使用メモリ | 67,484 KB |
最終ジャッジ日時 | 2025-10-05 13:57:57 |
合計ジャッジ時間 | 13,484 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
ソースコード
import static java.lang.Math.*; import static java.util.Arrays.*; import java.io.*; import java.lang.reflect.*; import java.util.*; import java.util.ArrayList; import java.util.concurrent.*; import java.util.function.*; import java.util.stream.*; public class Main{ public static void main(String[] args) throws Exception{ MyReader in = new MyReader(System.in); MyWriter out = new MyWriter(System.out,false),log = new MyWriter(System.err,true); int T = Solver.multi ? in.it() : 1; while (T-- > 0) Optional.ofNullable(new Solver(in,out,log).solve()).ifPresent(out::println); out.flush(); } } class Solver extends BaseSolver{ public Solver(MyReader in,MyWriter out,MyWriter log){ super(in,out,log); } public static boolean multi = false; public Object solve(){ int N = in.it(),M = in.it(); int T = in.it(); int[] A = in.idx(M); SegmentTree<Data, Integer> seg = new SegmentTree<>(N){ @Override protected Data e(){ return new Data(infI,-infI,-1,-1); } @Override protected Data init(int i){ return new Data(0,0,i,i); } @Override protected void agg(Data v,Data a,Data b){ v.i = a.m <= b.m ? a.i : b.i; v.I = a.M >= b.M ? a.I : b.I; v.m = min(a.m,b.m); v.M = max(a.M,b.M); } @Override protected void map(Data v,Integer f){ v.m += f; v.M += f; } }; for (var a:A) seg.upd(a,1); int ans = seg.get(0,N).M; while (true) { var d = seg.get(0,N); seg.upd(d.i,T); seg.upd(d.I,-1); d = seg.get(0,N); if (ans < d.M) break; ans = d.M; } return ans; } <T extends BaseV> void log(Seg<T, ?> seg,int n){ T[] a = (T[]) new BaseV[n]; for (int i = 0;i < n;i++) a[i] = seg.get(i); log.println(a); } private int[][] rle(int[] S){ List<int[]> list = new ArrayList<>(); int[] cur = {S[0], 1}; for (int i = 1;i < S.length;i++) if (cur[0] == S[i]) cur[1]++; else { list.add(cur); cur = new int[]{S[i], 1}; } list.add(cur); return list.stream().toArray(n -> new int[n][]); } } class Data extends BaseV{ public int m,M,i,I; public Data(int m,int M,int i,int I){ this.m = m; this.M = M; this.i = i; this.I = I; } @Override public String toString(){ return "" +m; } } abstract class Seg<V extends BaseV, F> { private int n; private V[] ret,val; private F[] lazy; protected Seg(int n){ this.n = n; ret = Util.cast(new BaseV[]{e(), e()}); val = Util.cast(new BaseV[n <<1]); lazy = Util.cast(new Object[n]); for (int i = -1;++i < n;) (val[i +n] = init(i)).sz = 1; for (int i = n;--i > 0;merge(i)) (val[i] = e()).sz = val[i <<1].sz +val[i <<1 |1].sz; } public void upd(int i,F f){ prop(i +n,f); } public void upd(int l,int r,F f){ for (l += n,r += n;l < r;l >>= 1,r >>= 1) { if ((l &1) == 1) prop(l++,f); if ((r &1) == 1) prop(--r,f); } } public V get(int i){ return val[i +n]; } public V get(int l,int r){ int i = 0; ret[i] = e(); i ^= 1; for (var v:getList(l,r)) { agg(ret[i],ret[i ^1],v); ret[i].sz = ret[i ^= 1].sz +v.sz; } return ret[i ^1]; } public V[] getList(int l,int r){ int sz = 0; for (int li = l += n,ri = r += n;li < ri;li = li +1 >>1,ri >>= 1) sz += (li &1) +(ri &1); V[] arr = Util.cast(Array.newInstance(e().getClass(),sz)); for (int i = 0;l < r;l >>= 1,r >>= 1) { if ((l &1) > 0) arr[i++] = val[l++]; if ((r &1) > 0) arr[--sz] = val[--r]; } return arr; } public V[] getPath(int i){ int sz = 32 -Integer.numberOfLeadingZeros(i +n); V[] arr = Util.cast(Array.newInstance(e().getClass(),sz)); for (i += n;0 < i;i >>= 1) arr[--sz] = val[i]; return arr; } protected V init(int i){ return e(); } protected abstract V e(); protected abstract void agg(V v,V a,V b); protected abstract void map(V v,F f); protected abstract F comp(F f,F g); protected void up(int l,int r){ for (l = oddPart(l +n),r = oddPart(r +n);l != r;) merge(l > r ? (l >>= 1) : (r >>= 1)); while (1 < l) merge(l >>= 1); } protected void down(int l,int r){ int i = 32 -Integer.numberOfLeadingZeros(n); for (l = oddPart(l +n),r = oddPart(r +n);i > 0;i--) { push(l >>i); push(r >>i); } } private void merge(int i){ agg(val[i],val[i <<1],val[i <<1 |1]); } private void push(int i){ if (lazy[i] != null) { prop(i <<1,lazy[i]); prop(i <<1 |1,lazy[i]); lazy[i] = null; } } private void prop(int i,F f){ map(val[i],f); if (i < n) { lazy[i] = lazy[i] == null ? f : comp(lazy[i],f); if (val[i].fail) { push(i); merge(i); } } } private int oddPart(int i){ return i /(i &-i); } } abstract class SegmentTree<V extends BaseV, F> extends Seg<V, F>{ public SegmentTree(int n){ super(n); } @Override protected F comp(F f,F g){ return null; } @Override public void upd(int i,F f){ super.upd(i,f); up(i,i +1); } } abstract class DisjointSparseTable<V extends BaseV> { private int n,k; private V[][] dat; public DisjointSparseTable(int n){ this.n = Integer.highestOneBit(n -1) <<1; k = Integer.SIZE -Integer.numberOfLeadingZeros(this.n); dat = Util.cast(new BaseV[k][this.n]); setAll(dat[0],this::init); for (int i = 0;i < this.n;i++) dat[0][i].sz = 1; build(); } private void build(){ V[][] dat = this.dat; for (int kk = 1;kk < k;kk++) { setAll(dat[kk],i -> e()); int l = 1 <<kk; for (int s = 0;s < n;s += l) { int m = s +s +l >>1; dat[kk][m -1] = init(m -1); dat[kk][m] = init(m); dat[kk][m -1].sz = dat[kk][m].sz = 1; for (int j = 1;j <<1 < l;j++) { agg(dat[kk][m -1 -j],dat[0][m -1 -j],dat[kk][m -j]); agg(dat[kk][m +j],dat[kk][m +j -1],dat[0][m +j]); dat[kk][m -1 -j].sz = dat[kk][m +j].sz = j +1; } } } } protected abstract V e(); protected abstract V init(int i); protected abstract void agg(V v,V a,V b); protected V get(int i){ return dat[0][i]; } protected V get(int l,int r){ if (l >= r) return null; if (r -l == 1) return get(l); int k = Integer.SIZE -Integer.numberOfLeadingZeros(l ^r -1); V ret = e(); agg(ret,dat[k][l],dat[k][r -1]); return ret; } } class Edge<L> { public int id,u,v; public L val; public Edge<L> re; public Edge(int id,int u,int v,L val){ this.id = id; this.u = u; this.v = v; this.val = val; } } class Graph<L> { protected int n; protected MyList<Edge<L>> es; private Edge<L>[][] go,bk; private int[] cntgo,cntbk; private boolean built; public Graph(int n,boolean dir){ this.n = n; go = Util.cast(new Edge[n][]); bk = dir ? Util.cast(new Edge[n][]) : go; fill(go,new Edge[0]); fill(bk,new Edge[0]); es = new MyList<>(); cntgo = new int[n]; cntbk = dir ? new int[n] : cntgo; } public int size(){ return n; } protected L inv(L l){ return l; } public void addEdge(int u,int v){ addEdge(u,v,null); } public void addEdge(int u,int v,L l){ var e = new Edge<>(es.size(),u,v,l); var re = new Edge<>(e.id,e.v,e.u,inv(e.val)); es.add(e); re.re = e; e.re = re; } public Edge<L>[] go(int u){ if (!built) build(); return go[u]; } public Edge<L>[] bk(int u){ if (!built) build(); return bk[u]; } private void build(){ for (var e:es) { cntgo[e.u]++; cntbk[e.v]++; } for (var e:es) { if (go[e.u].length == 0) go[e.u] = Util.cast(new Edge[cntgo[e.u]]); if (bk[e.v].length == 0) bk[e.v] = Util.cast(new Edge[cntbk[e.v]]); } for (var e:es) { go[e.u][--cntgo[e.u]] = e; bk[e.v][--cntbk[e.v]] = e.re; } built = true; } public void clear(){ Edge<L>[] empty = Util.cast(new Edge[0]); for (var e:es) go[e.u] = bk[e.v] = empty; es.clear(); built = false; } } abstract class BaseV{ public int sz; public boolean fail; } class MyList<E> implements Iterable<E>{ private E[] arr; private int hd,tl; public MyList(){ this(16); } public MyList(int n){ arr = Util.cast(new Object[Integer.highestOneBit(max(16,n) -1) <<1]); } public MyList(MyList<E> org){ this(org.size() +1); System.arraycopy(org.arr,0,arr,0,tl = org.size()); } public MyList(Collection<E> col){ this(col.size() +1); col.forEach(this::add); } public void add(E t){ addLast(t); } public void addFirst(E e){ hd = hd -1 &arr.length -1; arr[hd] = e; if (hd == tl) grow(); } public void addLast(E e){ arr[tl] = e; tl = tl +1 &arr.length -1; if (hd == tl) grow(); } public E peek(){ return peekFirst(); } public E peekFirst(){ return arr[hd]; } public E peekLast(){ return arr[tl -1 &arr.length -1]; } public E poll(){ return pollFirst(); } public E pollFirst(){ E ret = arr[hd]; hd = hd +1 &arr.length -1; return ret; } public E pollLast(){ tl = tl -1 &arr.length -1; return arr[tl]; } public E get(int i){ return arr[hd +i &arr.length -1]; } public E remove(int i){ i = hd +i &arr.length -1; E ret = arr[i]; tl = tl -1 &arr.length -1; while (i != tl) { arr[i] = arr[i +1 &arr.length -1]; i = i +1 &arr.length -1; } return ret; } public E removeFast(int i){ swap(i,size() -1); return pollLast(); } public void swap(int i,int j){ i = hd +i &arr.length -1; j = hd +j &arr.length -1; Util.swap(arr,i,j); } public void set(int i,E t){ arr[hd +i &arr.length -1] = t; } public void clear(){ tl = hd; } public int size(){ return tl -hd &arr.length -1; } public boolean isEmpty(){ return tl == hd; } public void sort(){ sort(Util.cast(Comparator.naturalOrder())); } public void sort(Comparator<E> cmp){ int size = size(); if (hd > tl) System.arraycopy(arr,hd,arr,tl,arr.length -hd); else System.arraycopy(arr,hd,arr,0,tl -hd); Arrays.sort(arr,hd = 0,tl = size,cmp); } public <U> MyList<U> map(Function<E, U> func){ MyList<U> ret = new MyList<>(size()); forEach(t -> ret.add(func.apply(t))); return ret; } public MyList<E> rev(){ MyList<E> ret = new MyList<>(size()); for (int i = size();i-- > 0;) ret.add(get(i)); return ret; } public int[] toIntArray(ToIntFunction<E> f){ return Util.arrI(size(),i -> f.applyAsInt(get(i))); } public E[] toArray(){ if (hd == tl) return Util.cast(new Object[0]); E[] ret = Util.cast(Array.newInstance(arr[0].getClass(),size())); if (hd < tl) System.arraycopy(arr,hd,ret,0,tl -hd); else { System.arraycopy(arr,hd,ret,0,arr.length -hd); System.arraycopy(arr,0,ret,arr.length -hd,tl); } return ret; } private void grow(){ E[] newarr = Util.cast(new Object[arr.length <<1]); System.arraycopy(arr,hd,newarr,0,arr.length -hd); System.arraycopy(arr,0,newarr,arr.length -hd,tl); hd = 0; tl = arr.length; arr = newarr; } @Override public Iterator<E> iterator(){ return new Iterator<>(){ int i = 0; @Override public boolean hasNext(){ return i < size(); } @Override public E next(){ return get(i++); } }; } public Stream<E> stream(){ return StreamSupport.stream(Spliterators.spliteratorUnknownSize(iterator(),0),false); } } class BaseSolver extends Util{ public MyReader in; public MyWriter out,log; public BaseSolver(MyReader in,MyWriter out,MyWriter log){ this.in = in; this.out = out; this.log = log; } public int[][] addId(int[][] T){ return arr(new int[T.length][],i -> { int[] t = copyOf(T[i],T[i].length +1); t[t.length -1] = i; return t; }); } public long inv(long x){ return pow(x,mod -2); } public long inv(long x,long mod){ return (extendGcd(x,mod)[0] +mod) %mod; } public long pow(long x,long n){ return pow(x,n,mod); } public long pow(long x,long n,long mod){ long ret = 1; for (x %= mod;0 < n;x = x *x %mod,n >>= 1) if ((n &1) == 1) ret = ret *x %mod; return ret; } public int bSearchI(int o,int n,IntPredicate judge){ for (int m = 0;1 < abs(n -o);) m = judge.test(m = o +n >>1) ? (o = m) : (n = m); return o; } public long bSearchL(long o,long n,LongPredicate judge){ for (long m = 0;1 < abs(n -o);) m = judge.test(m = o +n >>1) ? (o = m) : (n = m); return o; } public double bSearchD(double o,double n,DoublePredicate judge){ for (double m,c = 0;c < 100;c++) m = judge.test(m = (o +n) /2) ? (o = m) : (n = m); return o; } public long gcd(long... arr){ long ret = arr[0]; for (int i = 1;i < arr.length;i++) ret = gcd(ret,arr[i]); return ret; } public long gcd(long a,long b){ while (0 < b) { long t = a; a = b; b = t %b; } return a; } public long[] extendGcd(long a,long b){ long x0 = 1,y0 = 0,x1 = 0,y1 = 1; while (b != 0) { long q = a /b,t = a %b,tx = x1,ty = y1; a = b; b = t; x1 = x0 -q *x1; y1 = y0 -q *y1; x0 = tx; y0 = ty; } return new long[]{x0, y0, a}; } public long lcm(long a,long b){ return b /gcd(a,b) *a; } public long ceil(long a,long b){ return (a +b -1) /b; } public int[] lis(int[] arr){ int n = arr.length; int[] lis = new int[n],idx = new int[n],par = new int[n]; fill(lis,infI); int l = 0; for (int i = 0;i < n;i++) { int a = arr[i]; int pos = bSearchI(n -1,-1,ii -> lis[ii] >= a); lis[pos] = a; idx[pos] = i; if (pos > 0) par[i] = idx[pos -1]; l = max(l,pos +1); } int[] result = new int[l]; for (int i = l -1,cur = idx[l -1];i >= 0;i--) { result[i] = arr[cur]; cur = par[cur]; } return result; } public void shift(char[][] S,char offset){ for (var s:S) shift(s,offset); } public void shift(char[] s,char offset){ for (int i = 0;i < s.length;i++) s[i] -= offset; } public HashSet<Integer> set(int[] arr){ HashSet<Integer> set = new HashSet<>(); for (var a:arr) set.add(a); return set; } public TreeSet<Integer> treeset(int[] arr){ TreeSet<Integer> set = new TreeSet<>(); for (var a:arr) set.add(a); return set; } } class Util{ public static String yes = "Yes",no = "No"; public static int infI = (1 <<30) -1,mod = 998244353; public static long infL = (1L <<61 |1 <<30) -1; public static Random rd = ThreadLocalRandom.current(); private long st = System.currentTimeMillis(); protected long elapsed(){ return System.currentTimeMillis() -st; } protected void reset(){ st = System.currentTimeMillis(); } public static int[] arrI(int N,IntUnaryOperator f){ return IntStream.range(0,N).map(f).toArray(); } public static long[] arrL(int N,IntToLongFunction f){ return IntStream.range(0,N).mapToLong(f).toArray(); } public static double[] arrD(int N,IntToDoubleFunction f){ return IntStream.range(0,N).mapToDouble(f).toArray(); } public static <T> T[] arr(T[] arr,IntFunction<T> f){ setAll(arr,f); return arr; } @SuppressWarnings("unchecked") public static <T> T cast(Object obj){ return (T) obj; } public static <T> void swap(T[] arr,int i,int j){ T t = arr[i]; arr[i] = arr[j]; arr[j] = t; } public static int min(int... arr){ int ret = arr[0]; for (int i = 1;i < arr.length;i++) ret = Math.min(ret,arr[i]); return ret; } public static long min(long... arr){ long ret = arr[0]; for (int i = 1;i < arr.length;i++) ret = Math.min(ret,arr[i]); return ret; } public static double min(double... arr){ double ret = arr[0]; for (int i = 1;i < arr.length;i++) ret = Math.min(ret,arr[i]); return ret; } public static int max(int... arr){ int ret = arr[0]; for (int i = 1;i < arr.length;i++) ret = Math.max(ret,arr[i]); return ret; } public static long max(long... arr){ long ret = arr[0]; for (int i = 1;i < arr.length;i++) ret = Math.max(ret,arr[i]); return ret; } public static double max(double... arr){ double ret = arr[0]; for (int i = 1;i < arr.length;i++) ret = Math.max(ret,arr[i]); return ret; } public static double sum(double... A){ double ret = 0; for (var a:A) ret += a; return ret; } public static long sum(int... A){ long ret = 0; for (var a:A) ret += a; return ret; } public static long sum(long... A){ long ret = 0; for (var a:A) ret += a; return ret; } } class MyReader{ private byte[] buf = new byte[1 <<16]; private int ptr,tail; private InputStream in; public 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; } public int it(){ return toIntExact(lg()); } public int[] it(int N){ return Util.arrI(N,i -> it()); } public int[][] it(int H,int W){ return Util.arr(new int[H][],i -> it(W)); } public int idx(){ return it() -1; } public int[] idx(int N){ return Util.arrI(N,i -> idx()); } public int[][] idx(int H,int W){ return Util.arr(new int[H][],i -> idx(W)); } public 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; } public long[] lg(int N){ return Util.arrL(N,i -> lg()); } public long[][] lg(int H,int W){ return Util.arr(new long[H][],i -> lg(W)); } public double dbl(){ String str = str(); return Double.parseDouble(str); } public double[] dbl(int N){ return Util.arrD(N,i -> dbl()); } public double[][] dbl(int H,int W){ return Util.arr(new double[H][],i -> dbl(W)); } public char[] ch(){ return str().toCharArray(); } public char[][] ch(int H){ return Util.arr(new char[H][],i -> ch()); } public String line(){ StringBuilder sb = new StringBuilder(); for (byte c;(c = read()) != '\n';) sb.append((char) c); return sb.toString(); } public String str(){ StringBuilder sb = new StringBuilder(); sb.append((char) nextPrintable()); for (byte c;isPrintable(c = read());) sb.append((char) c); return sb.toString(); } public String[] str(int N){ return Util.arr(new String[N],i -> str()); } public String[][] str(int H,int W){ return Util.arr(new String[H][],i -> str(W)); } } class MyWriter{ private OutputStream out; private byte[] buf = new byte[1 <<16],ibuf = new byte[20]; private int tail; private boolean autoflush; public MyWriter(OutputStream out,boolean autoflush){ this.out = out; this.autoflush = autoflush; } public void flush(){ try { out.write(buf,0,tail); tail = 0; } catch (IOException e) { e.printStackTrace(); } } private void write(byte b){ buf[tail++] = b; if (tail == buf.length) flush(); } 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); while (i < ibuf.length) write(ibuf[i++]); } private void print(Object obj){ if (obj instanceof Boolean) print((boolean) obj ? Util.yes : Util.no); else if (obj instanceof Integer) write((int) obj); else if (obj instanceof Long) write((long) obj); else if (obj instanceof char[]) for (char b:(char[]) obj) 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()); } public void println(Object obj){ if (obj == null) obj = "null"; if (obj instanceof Iterable<?>) for (Object e:(Iterable<?>) obj) 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); write((byte) '\n'); if (autoflush) flush(); } } public void printlns(Object... obj){ print(obj); write((byte) '\n'); if (autoflush) flush(); } }