結果
| 問題 |
No.1441 MErGe
|
| コンテスト | |
| ユーザー |
 cyclerecycle9
|
| 提出日時 | 2021-07-28 22:26:41 |
| 言語 | Java (openjdk 23) |
| 結果 |
RE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 12,577 bytes |
| コンパイル時間 | 2,893 ms |
| コンパイル使用メモリ | 92,172 KB |
| 実行使用メモリ | 37,412 KB |
| 最終ジャッジ日時 | 2024-09-13 19:17:10 |
| 合計ジャッジ時間 | 6,687 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | RE * 2 |
| other | RE * 28 |
ソースコード
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.*;
import java.io.File;
import java.io.FileDescriptor;
import java.io.FileOutputStream;
import java.io.OutputStream;
import java.io.UncheckedIOException;
import java.lang.reflect.Field;
import java.nio.CharBuffer;
import java.nio.charset.CharacterCodingException;
import java.nio.charset.CharsetEncoder;
import java.nio.charset.StandardCharsets;
public class Main {
static final long MOD=1000000007;
static final long MOD1=998244353;
static int ans=0;
public static void main(String[] args){
PrintWriter out = new PrintWriter(System.out);
InputReader sc=new InputReader(System.in);
FastPrintStream pw = new FastPrintStream();
int N = sc.nextInt();
int Q = sc.nextInt();
long[] A = new long[N+1];
for (int i = 1; i < A.length; i++) {
A[i] = A[i-1] + sc.nextLong();
}
BIT bit = new BIT(N+1);
TreeSet<Integer> treeSet = new TreeSet<>();
for (int i = 1; i < A.length; i++) {
bit.add(i, 1);
treeSet.add(i);
}
for (int i = 0; i < Q; i++) {
int T = sc.nextInt();
int l = sc.nextInt();
int r = sc.nextInt();
if (T==1) {
int l1 = get(l, bit, N);
int r1 = get(r, bit, N);
for (int j = l; j < r; j++) {
int x = treeSet.ceiling(l1);
if(x>=r1)throw new ArrayIndexOutOfBoundsException();
treeSet.remove(x);
bit.add(x, -1);
}
}else {
int l1 = 0;
if (l>1) {
l1 = get(l-1, bit, N);
}
int r1 = get(r, bit, N);
pw.println(A[r1]-A[l1]);
}
}
pw.flush();
}
static int get(int l,BIT bit,int N){
int from=0;
int to=N;
while ((to-from)>=1) {
int mid=(to-from)/2+from;
if (bit.sum(mid)>=l){
to=mid;
}
else {
from=mid+1;
}
}
return to;
}
static class BIT{
int size;
int[] bit;
public BIT(int n) {
size=n;
bit=new int[size];
}
public int sum(int i){
int s=0;
while (i>0) {
s+=bit[i];
i-=(i&(-i));//iの二進表現での一番右の１を消す
}
return s;
}
public void add(int i,int x) {
while (i<size) {
bit[i]+=x;
i+= (i&(-i));//iの二進表現での一番右の１（区間の大きさ）を足すと次に足す区間へ
}
}
}
static class InputReader {
private InputStream in;
private byte[] buffer = new byte[1024];
private int curbuf;
private int lenbuf;
public InputReader(InputStream in) {
this.in = in;
this.curbuf = this.lenbuf = 0;
}
public boolean hasNextByte() {
if (curbuf >= lenbuf) {
curbuf = 0;
try {
lenbuf = in.read(buffer);
} catch (IOException e) {
throw new InputMismatchException();
}
if (lenbuf <= 0)
return false;
}
return true;
}
private int readByte() {
if (hasNextByte())
return buffer[curbuf++];
else
return -1;
}
private boolean isSpaceChar(int c) {
return !(c >= 33 && c <= 126);
}
private void skip() {
while (hasNextByte() && isSpaceChar(buffer[curbuf]))
curbuf++;
}
public boolean hasNext() {
skip();
return hasNextByte();
}
public String next() {
if (!hasNext())
throw new NoSuchElementException();
StringBuilder sb = new StringBuilder();
int b = readByte();
while (!isSpaceChar(b)) {
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
public int nextInt() {
if (!hasNext())
throw new NoSuchElementException();
int c = readByte();
while (isSpaceChar(c))
c = readByte();
boolean minus = false;
if (c == '-') {
minus = true;
c = readByte();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res = res * 10 + c - '0';
c = readByte();
} while (!isSpaceChar(c));
return (minus) ? -res : res;
}
public long nextLong() {
if (!hasNext())
throw new NoSuchElementException();
int c = readByte();
while (isSpaceChar(c))
c = readByte();
boolean minus = false;
if (c == '-') {
minus = true;
c = readByte();
}
long res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res = res * 10 + c - '0';
c = readByte();
} while (!isSpaceChar(c));
return (minus) ? -res : res;
}
public double nextDouble() {
return Double.parseDouble(next());
}
public int[] nextIntArray(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = nextInt();
return a;
}
public double[] nextDoubleArray(int n) {
double[] a = new double[n];
for (int i = 0; i < n; i++)
a[i] = nextDouble();
return a;
}
public long[] nextLongArray(int n) {
long[] a = new long[n];
for (int i = 0; i < n; i++)
a[i] = nextLong();
return a;
}
public char[][] nextCharMap(int n, int m) {
char[][] map = new char[n][m];
for (int i = 0; i < n; i++)
map[i] = next().toCharArray();
return map;
}
}
}
class FastPrintStream implements AutoCloseable {
private static final int INT_MAX_LEN = 11;
private static final int LONG_MAX_LEN = 20;
private int precision = 9;
private static final int BUF_SIZE = 1 << 14;
private static final int BUF_SIZE_MINUS_INT_MAX_LEN = BUF_SIZE - INT_MAX_LEN;
private static final int BUF_SIZE_MINUS_LONG_MAX_LEN = BUF_SIZE - LONG_MAX_LEN;
private final byte[] buf = new byte[BUF_SIZE];
private int ptr = 0;
private final Field strField;
private final CharsetEncoder encoder;
private final OutputStream out;
public FastPrintStream(OutputStream out) {
this.out = out;
Field f;
try {
f = String.class.getDeclaredField("value");
f.setAccessible(true);
} catch (NoSuchFieldException | SecurityException e) {
f = null;
}
this.strField = f;
this.encoder = StandardCharsets.US_ASCII.newEncoder();
}
public FastPrintStream(File file) throws IOException {
this(new FileOutputStream(file));
}
public FastPrintStream(String filename) throws IOException {
this(new File(filename));
}
public FastPrintStream() {
this(new FileOutputStream(FileDescriptor.out));
}
public FastPrintStream println() {
if (ptr == BUF_SIZE) internalFlush();
buf[ptr++] = (byte) '\n';
return this;
}
public FastPrintStream println(Object o) {
return print(o).println();
}
public FastPrintStream println(String s) {
return print(s).println();
}
public FastPrintStream println(char[] s) {
return print(s).println();
}
public FastPrintStream println(char c) {
return print(c).println();
}
public FastPrintStream println(int x) {
return print(x).println();
}
public FastPrintStream println(long x) {
return print(x).println();
}
public FastPrintStream println(double d, int precision) {
return print(d, precision).println();
}
public FastPrintStream println(double d) {
return print(d).println();
}
private FastPrintStream print(byte[] bytes) {
int n = bytes.length;
if (ptr + n > BUF_SIZE) {
internalFlush();
try {
out.write(bytes);
} catch (IOException e) {
throw new UncheckedIOException(e);
}
} else {
System.arraycopy(bytes, 0, buf, ptr, n);
ptr += n;
}
return this;
}
public FastPrintStream print(Object o) {
return print(o.toString());
}
public FastPrintStream print(String s) {
if (strField == null) {
return print(s.getBytes());
} else {
try {
Object value = strField.get(s);
if (value instanceof byte[]) {
return print((byte[]) value);
} else {
return print((char[]) value);
}
} catch (IllegalAccessException e) {
return print(s.getBytes());
}
}
}
public FastPrintStream print(char[] s) {
try {
return print(encoder.encode(CharBuffer.wrap(s)).array());
} catch (CharacterCodingException e) {
byte[] bytes = new byte[s.length];
for (int i = 0; i < s.length; i++) {
bytes[i] = (byte) s[i];
}
return print(bytes);
}
}
public FastPrintStream print(char c) {
if (ptr == BUF_SIZE) internalFlush();
buf[ptr++] = (byte) c;
return this;
}
public FastPrintStream print(int x) {
if (ptr > BUF_SIZE_MINUS_INT_MAX_LEN) internalFlush();
if (-10 < x && x < 10) {
if (x < 0) {
buf[ptr++] = '-';
x = -x;
}
buf[ptr++] = (byte) ('0' + x);
return this;
}
int d;
if (x < 0) {
if (x == Integer.MIN_VALUE) {
buf[ptr++] = '-'; buf[ptr++] = '2'; buf[ptr++] = '1'; buf[ptr++] = '4';
buf[ptr++] = '7'; buf[ptr++] = '4'; buf[ptr++] = '8'; buf[ptr++] = '3';
buf[ptr++] = '6'; buf[ptr++] = '4'; buf[ptr++] = '8';
return this;
}
d = len(x = -x);
buf[ptr++] = '-';
} else {
d = len(x);
}
int j = ptr += d;
while (x > 0) {
buf[--j] = (byte) ('0' + (x % 10));
x /= 10;
}
return this;
}
public FastPrintStream print(long x) {
if ((int) x == x) return print((int) x);
if (ptr > BUF_SIZE_MINUS_LONG_MAX_LEN) internalFlush();
int d;
if (x < 0) {
if (x == Long.MIN_VALUE) {
buf[ptr++] = '-'; buf[ptr++] = '9'; buf[ptr++] = '2'; buf[ptr++] = '2';
buf[ptr++] = '3'; buf[ptr++] = '3'; buf[ptr++] = '7'; buf[ptr++] = '2';
buf[ptr++] = '0'; buf[ptr++] = '3'; buf[ptr++] = '6'; buf[ptr++] = '8';
buf[ptr++] = '5'; buf[ptr++] = '4'; buf[ptr++] = '7'; buf[ptr++] = '7';
buf[ptr++] = '5'; buf[ptr++] = '8'; buf[ptr++] = '0'; buf[ptr++] = '8';
return this;
}
d = len(x = -x);
buf[ptr++] = '-';
} else {
d = len(x);
}
int j = ptr += d;
while (x > 0) {
buf[--j] = (byte) ('0' + (x % 10));
x /= 10;
}
return this;
}
public FastPrintStream print(double d, int precision) {
if (d < 0) {
print('-');
d = -d;
}
d += Math.pow(10, -precision) / 2;
print((long) d).print('.');
d -= (long) d;
for(int i = 0; i < precision; i++){
d *= 10;
print((int) d);
d -= (int) d;
}
return this;
}
public FastPrintStream print(double d) {
return print(d, precision);
}
public void setPrecision(int precision) {
this.precision = precision;
}
private void internalFlush() {
try {
out.write(buf, 0, ptr);
ptr = 0;
} catch (IOException e) {
throw new UncheckedIOException(e);
}
}
public void flush() {
try {
out.write(buf, 0, ptr);
out.flush();
ptr = 0;
} catch (IOException e) {
throw new UncheckedIOException(e);
}
}
public void close() {
try {
out.close();
} catch (IOException e) {
throw new UncheckedIOException(e);
}
}
private static int len(int x) {
return
x >= 1000000000 ? 10 :
x >= 100000000 ? 9 :
x >= 10000000 ? 8 :
x >= 1000000 ? 7 :
x >= 100000 ? 6 :
x >= 10000 ? 5 :
x >= 1000 ? 4 :
x >= 100 ? 3 :
x >= 10 ? 2 : 1;
}
private static int len(long x) {
return
x >= 1000000000000000000L ? 19 :
x >= 100000000000000000L ? 18 :
x >= 10000000000000000L ? 17 :
x >= 1000000000000000L ? 16 :
x >= 100000000000000L ? 15 :
x >= 10000000000000L ? 14 :
x >= 1000000000000L ? 13 :
x >= 100000000000L ? 12 :
x >= 10000000000L ? 11 : 10;
}
}