結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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();
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0