結果
| 問題 |
No.2333 Slime Structure
|
| コンテスト | |
| ユーザー |
 tenten
|
| 提出日時 | 2023-06-01 10:07:37 |
| 言語 | Java (openjdk 23) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,769 bytes |
| コンパイル時間 | 4,019 ms |
| コンパイル使用メモリ | 86,948 KB |
| 実行使用メモリ | 164,928 KB |
| 最終ジャッジ日時 | 2024-12-28 14:41:36 |
| 合計ジャッジ時間 | 88,767 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 19 WA * 5 TLE * 7 |
ソースコード
import java.io.*;
import java.util.*;
import java.util.stream.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner();
int n = sc.nextInt();
TreeMap<Long, Integer> strengths = new TreeMap<>();
TreeMap<Long, Integer> compress = new TreeMap<>();
long current = 0;
for (int i = 0; i < n; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
strengths.put(current, a);
compress.put(current, null);
current += b;
}
compress.put(current, null);
int q = sc.nextInt();
int[] types = new int[q];
long[] lefts = new long[q];
long[] rights = new long[q];
for (int i = 0; i < q; i++) {
types[i] = sc.nextInt();
lefts[i] = sc.nextLong();
rights[i] = sc.nextLong();
if (types[i] == 1) {
compress.put(lefts[i] - 1, null);
compress.put(lefts[i], null);
} else {
compress.put(lefts[i] - 1, null);
compress.put(rights[i], null);
compress.put(lefts[i], null);
compress.put(rights[i] - 1, null);
}
}
int idx = 0;
long prev = -1;
long[] sizes = new long[compress.size()];
long[] values = new long[compress.size()];
for (long x : compress.keySet()) {
compress.put(x, idx);
if (prev >= 0) {
sizes[idx - 1] = x - prev;
values[idx - 1] = strengths.floorEntry(prev).getValue();
}
prev = x;
idx++;
}
SegmentTree st = new SegmentTree(idx);
for (int i = 0; i < sizes.length; i++) {
st.setValue(i, sizes[i] * values[i]);
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < q; i++) {
if (types[i] == 1) {
int x = compress.get(lefts[i] - 1);
st.setValue(x, rights[i]);
} else {
sb.append(st.getMax(compress.get(lefts[i] - 1), compress.get(rights[i]))).append("\n");
}
}
System.out.print(sb);
}
static class SegmentTree {
int size;
long[] lefts;
long[] rights;
long[] maxes;
long[] alls;
public SegmentTree(int x) {
size = 1;
while (x > size) {
size <<= 1;
}
lefts = new long[size * 2 - 1];
rights = new long[size * 2 - 1];
maxes = new long[size * 2 - 1];
alls = new long[size * 2 - 1];
}
public void setValue(int idx, long v) {
int current = size - 1 + idx;
lefts[current] = v;
rights[current] = v;
maxes[current] = v;
alls[current] = v;
setTreeValue((current - 1) / 2);
}
private void setTreeValue(int idx) {
alls[idx] = alls[idx * 2 + 1] + alls[idx * 2 + 2];
lefts[idx] = Math.max(alls[idx * 2 + 1] + lefts[idx * 2 + 2], lefts[idx * 2 + 1]);
rights[idx] = Math.max(rights[idx * 2 + 1] + alls[idx * 2 + 2], rights[idx * 2 + 2]);
maxes[idx] = Math.max(rights[idx * 2 + 1] + lefts[idx * 2 + 2], Math.max(maxes[idx * 2 + 1], maxes[idx * 2 + 2]));
if (idx > 0) {
setTreeValue((idx - 1) / 2);
}
}
public long getMax(int left, int right) {
return getTreeMax(0, 0, size, left, right);
}
private long getTreeMax(int idx, int min, int max, int left, int right) {
if (max <= left || right <= min) {
return Long.MIN_VALUE;
}
if (left <= min && max <= right) {
return maxes[idx];
}
return Math.max(getRightMax(idx * 2 + 1, min, (min + max) / 2, left, right) + getLeftMax(idx * 2 + 2, (min + max) / 2, max, left, right),
Math.max(getTreeMax(idx * 2 + 1, min, (min + max) / 2, left, right), getTreeMax(idx * 2 + 2, (min + max) / 2, max, left, right)));
}
private long getLeftMax(int idx, int min, int max, int left, int right) {
if (min < left || max <= left || right <= min) {
return Long.MIN_VALUE / 2;
}
if (right >= max) {
return lefts[idx];
}
return Math.max(getAll(idx * 2 + 1, min, (min + max) / 2, left, right) + getLeftMax(idx * 2 + 2, (min + max) / 2, max, left, right), getLeftMax(idx * 2 + 1, min, (min + max) / 2, left, right));
}
private long getRightMax(int idx, int min, int max, int left, int right) {
if (right < max || max <= left || right <= min) {
return Long.MIN_VALUE / 2;
}
if (left <= min) {
return rights[idx];
}
return Math.max(getRightMax(idx * 2 + 1, min, (min + max) / 2, left, right) + getAll(idx * 2 + 2, (min + max) / 2, max, left, right), getRightMax(idx * 2 + 2, (min + max) / 2, max, left, right));
}
private long getAll(int idx, int min, int max, int left, int right) {
if (left <= min && max <= right) {
return alls[idx];
} else {
return Long.MIN_VALUE / 2;
}
}
}
}
class Utilities {
static String arrayToLineString(Object[] arr) {
return Arrays.stream(arr).map(x -> x.toString()).collect(Collectors.joining("\n"));
}
static String arrayToLineString(int[] arr) {
return String.join("\n", Arrays.stream(arr).mapToObj(String::valueOf).toArray(String[]::new));
}
}
class Scanner {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer("");
StringBuilder sb = new StringBuilder();
public Scanner() throws Exception {
}
public int nextInt() throws Exception {
return Integer.parseInt(next());
}
public long nextLong() throws Exception {
return Long.parseLong(next());
}
public double nextDouble() throws Exception {
return Double.parseDouble(next());
}
public int[] nextIntArray() throws Exception {
return Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
public String next() throws Exception {
while (!st.hasMoreTokens()) {
st = new StringTokenizer(br.readLine());
}
return st.nextToken();
}
}