結果
| 問題 | No.876 Range Compress Query |
| ユーザー |
 Grenache
|
| 提出日時 | 2019-09-06 22:08:54 |
| 言語 | Java (openjdk 23) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,871 bytes |
| コンパイル時間 | 4,641 ms |
| コンパイル使用メモリ | 85,672 KB |
| 実行使用メモリ | 79,608 KB |
| 最終ジャッジ日時 | 2024-06-24 18:04:27 |
| 合計ジャッジ時間 | 10,808 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 15 WA * 3 |
ソースコード
import java.io.*;import java.util.NoSuchElementException;public class Main_yukicoder876 {private static Scanner sc;private static Printer pr;private static void solve() {int n = sc.nextInt();int q = sc.nextInt();int[] a = sc.nextIntArray(n);RSQ_RAQ rsq_raq = new RSQ_RAQ(a);RSQ rsq = new RSQ(n);for (int i = 0; i < n - 1; i++) {if (a[i] != a[i + 1]) {rsq.add(i, 1);}}for (int i = 0; i < q; i++) {int query = sc.nextInt();int l = sc.nextInt() - 1;int r = sc.nextInt() - 1;if (query == 1) {int x = sc.nextInt();if (l > 0) {long tmp1 = rsq_raq.query(l - 1, l);long tmp2 = rsq_raq.query(l, l + 1);if (tmp1 != tmp2 && tmp1 == tmp2 + x) {rsq.add(l - 1, -1);} else if (tmp1 == tmp2 && tmp1 != tmp2 + x) {rsq.add(l - 1, 1);}}if (r < n - 1) {long tmp1 = rsq_raq.query(r, r + 1);long tmp2 = rsq_raq.query(r + 1, r + 2);if (tmp1 != tmp2 && tmp1 == tmp2 + x) {rsq.add(r, -1);} else if (tmp1 == tmp2 && tmp1 != tmp2 + x) {rsq.add(r, 1);}}rsq_raq.add(l, r + 1, x);} else {// for (int j = 0; j < n; j++) {// pr.printLongs(j, rsq.query(j, j + 1));// }pr.println(rsq.query(l, r) + 1);}}}// RSQ and RAQ by Segment Treestatic class RSQ_RAQ {long[] stAdd;// セグメント内のすべてに足す値long[] stSum;// セグメント内の合計値(除く上記のすべてに足す値)int n; // dataの要素数(2のべき乗に補正)// 各要素の値の範囲、合計値のオーバフローに注意public RSQ_RAQ(int[] data) {n = 1;while (n < data.length) {n *= 2;}stAdd = new long[2 * n - 1];stSum = new long[2 * n - 1];for (int i = 0, size = data.length; i < size; i++) {stSum[n - 1 + i] = data[i];}for (int i = n - 2; i >= 0; i--) {stSum[i] = stSum[2 * i + 1] + stSum[2 * i + 2];}}// l,r:0-indexed// [l,r)の値にaddvoid add(int l, int r, int x) {add(l, r, x, 0, 0, n);}void add(int l, int r, int x, int k, int ll, int rr) {if (ll >= l && rr <= r) {stAdd[k] += x;} else if (ll >= r || rr <= l) {// 交差なし} else {stSum[k] += (Math.min(r, rr) - Math.max(l, ll)) * x;int mm = (ll + rr) / 2;add(l, r, x, 2 * k + 1, ll, mm);add(l, r, x, 2 * k + 2, mm, rr);}}// l,r:0-indexed// [l,r)の和long query(int l, int r) {return query(l, r, 0, 0, n);}long query(int l, int r, int k, int ll, int rr) {long ret;if (ll >= l && rr <= r) {ret = stSum[k] + (rr - ll) * stAdd[k];} else if (ll >= r || rr <= l) {// 交差なしret = 0;} else {ret = (Math.min(r, rr) - Math.max(l, ll)) * stAdd[k];int mm = (ll + rr) / 2;ret += query(l, r, 2 * k + 1, ll, mm);ret += query(l, r, 2 * k + 2, mm, rr);}return ret;}}/*** Segment Tree による Range Sum Query*/static class RSQ {long[] st;int n;/*** n 個の要素を持つSegmentTreeを生成する** @param n 要素数*/RSQ(int n) {this.n = 1;while (this.n < n) {this.n *= 2;}st = new long[2 * this.n - 1];}/*** i 番目の要素に x を足す** @param i 対象となる要素(0-indexed)* @param x 追加する値*/void add(int i, int x) {i = n - 1 + i;st[i] += x;while (i > 0) {i = (i - 1) / 2;st[i] += x;}}/*** 指定した区間の合計値を返す** @param a 区間の端点。[a,b)(0-indexed)* @param b 区間の端点。[a,b)(0-indexed)* @return 指定された区間の合計値*/long query(int a, int b) {return query(a, b, 0, 0, n);}private long query(int a, int b, int i, int l, int r) {if (a >= r || b <= l) {return 0;}if (a <= l && b >= r) {return st[i];}return query(a, b, i * 2 + 1, l, (l + r) / 2) + query(a, b, i * 2 + 2, (l + r) / 2, r);}}// ---------------------------------------------------public static void main(String[] args) {sc = new Scanner(System.in);pr = new Printer(System.out);solve();pr.close();sc.close();}static class Scanner {BufferedReader br;Scanner(InputStream in) {br = new BufferedReader(new InputStreamReader(in));}private boolean isPrintable(int ch) {return ch >= '!' && ch <= '~';}private boolean isCRLF(int ch) {return ch == '\n' || ch == '\r' || ch == -1;}private int nextPrintable() {try {int ch;while (!isPrintable(ch = br.read())) {if (ch == -1) {throw new NoSuchElementException();}}return ch;} catch (IOException e) {throw new NoSuchElementException();}}String next() {try {int ch = nextPrintable();StringBuilder sb = new StringBuilder();do {sb.appendCodePoint(ch);} while (isPrintable(ch = br.read()));return sb.toString();} catch (IOException e) {throw new NoSuchElementException();}}int nextInt() {try {// parseInt from Integer.parseInt()boolean negative = false;int res = 0;int limit = -Integer.MAX_VALUE;int radix = 10;int fc = nextPrintable();if (fc < '0') {if (fc == '-') {negative = true;limit = Integer.MIN_VALUE;} else if (fc != '+') {throw new NumberFormatException();}fc = br.read();}int multmin = limit / radix;int ch = fc;do {int digit = ch - '0';if (digit < 0 || digit >= radix) {throw new NumberFormatException();}if (res < multmin) {throw new NumberFormatException();}res *= radix;if (res < limit + digit) {throw new NumberFormatException();}res -= digit;} while (isPrintable(ch = br.read()));return negative ? res : -res;} catch (IOException e) {throw new NoSuchElementException();}}long nextLong() {try {// parseLong from Long.parseLong()boolean negative = false;long res = 0;long limit = -Long.MAX_VALUE;int radix = 10;int fc = nextPrintable();if (fc < '0') {if (fc == '-') {negative = true;limit = Long.MIN_VALUE;} else if (fc != '+') {throw new NumberFormatException();}fc = br.read();}long multmin = limit / radix;int ch = fc;do {int digit = ch - '0';if (digit < 0 || digit >= radix) {throw new NumberFormatException();}if (res < multmin) {throw new NumberFormatException();}res *= radix;if (res < limit + digit) {throw new NumberFormatException();}res -= digit;} while (isPrintable(ch = br.read()));return negative ? res : -res;} catch (IOException e) {throw new NoSuchElementException();}}float nextFloat() {return Float.parseFloat(next());}double nextDouble() {return Double.parseDouble(next());}String nextLine() {try {int ch;while (isCRLF(ch = br.read())) {if (ch == -1) {throw new NoSuchElementException();}}StringBuilder sb = new StringBuilder();do {sb.appendCodePoint(ch);} while (!isCRLF(ch = br.read()));return sb.toString();} catch (IOException e) {throw new NoSuchElementException();}}int[] nextIntArray(int n) {int[] ret = new int[n];for (int i = 0; i < n; i++) {ret[i] = sc.nextInt();}return ret;}long[] nextLongArray(int n) {long[] ret = new long[n];for (int i = 0; i < n; i++) {ret[i] = sc.nextLong();}return ret;}int[][] nextIntArrays(int m, int n) {int[][] ret = new int[m][n];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {ret[j][i] = sc.nextInt();}}return ret;}void close() {try {br.close();} catch (IOException e) {// throw new NoSuchElementException();}}}static class Printer extends PrintWriter {Printer(OutputStream out) {super(out);}void printInts(int... a) {StringBuilder sb = new StringBuilder(32);for (int i = 0, size = a.length; i < size; i++) {if (i > 0) {sb.append(' ');}sb.append(a[i]);}println(sb);}void printLongs(long... a) {StringBuilder sb = new StringBuilder(64);for (int i = 0, size = a.length; i < size; i++) {if (i > 0) {sb.append(' ');}sb.append(a[i]);}println(sb);}void printStrings(String... a) {StringBuilder sb = new StringBuilder(32);for (int i = 0, size = a.length; i < size; i++) {if (i > 0) {sb.append(' ');}sb.append(a[i]);}println(sb);}}}