結果
問題 | No.833 かっこいい電車 |
ユーザー | 37zigen |
提出日時 | 2019-05-24 22:45:31 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 1,797 ms / 2,000 ms |
コード長 | 2,113 bytes |
コンパイル時間 | 2,605 ms |
コンパイル使用メモリ | 74,996 KB |
実行使用メモリ | 79,544 KB |
最終ジャッジ日時 | 2023-09-14 20:56:09 |
合計ジャッジ時間 | 30,124 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,797 ms
71,660 KB |
testcase_01 | AC | 134 ms
56,276 KB |
testcase_02 | AC | 128 ms
55,776 KB |
testcase_03 | AC | 138 ms
55,668 KB |
testcase_04 | AC | 128 ms
55,872 KB |
testcase_05 | AC | 130 ms
56,268 KB |
testcase_06 | AC | 126 ms
56,424 KB |
testcase_07 | AC | 137 ms
55,532 KB |
testcase_08 | AC | 124 ms
55,992 KB |
testcase_09 | AC | 124 ms
55,920 KB |
testcase_10 | AC | 1,294 ms
71,236 KB |
testcase_11 | AC | 1,518 ms
73,852 KB |
testcase_12 | AC | 739 ms
67,348 KB |
testcase_13 | AC | 639 ms
61,040 KB |
testcase_14 | AC | 1,247 ms
76,148 KB |
testcase_15 | AC | 810 ms
67,012 KB |
testcase_16 | AC | 668 ms
63,944 KB |
testcase_17 | AC | 694 ms
64,792 KB |
testcase_18 | AC | 1,452 ms
79,544 KB |
testcase_19 | AC | 665 ms
64,964 KB |
testcase_20 | AC | 362 ms
60,456 KB |
testcase_21 | AC | 1,292 ms
69,948 KB |
testcase_22 | AC | 896 ms
70,280 KB |
testcase_23 | AC | 715 ms
67,112 KB |
testcase_24 | AC | 875 ms
69,520 KB |
testcase_25 | AC | 1,411 ms
70,232 KB |
testcase_26 | AC | 747 ms
68,532 KB |
testcase_27 | AC | 1,086 ms
70,924 KB |
testcase_28 | AC | 920 ms
66,820 KB |
testcase_29 | AC | 1,008 ms
69,296 KB |
testcase_30 | AC | 843 ms
68,784 KB |
testcase_31 | AC | 1,255 ms
71,668 KB |
ソースコード
import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { new Main().run(); } class SegTree { int n; long[] v; public SegTree(int n_) { n = 1; while (n < n_) n *= 2; v = new long[2 * n - 1]; } void add(int k, long val) { k += n - 1; v[k] += val; while (k > 0) { k = (k - 1) / 2; v[k] = v[2 * k + 1] + v[2 * k + 2]; } } long sum(int a, int b) { return sum(0, n, a, b, 0); } long sum(int l, int r, int a, int b, int k) { if (a <= l && r <= b) return v[k]; else if (b <= l || r <= a) return 0; else { long lv = sum(l, (l + r) / 2, a, b, 2 * k + 1); long rv = sum((l + r) / 2, r, a, b, 2 * k + 2); return lv + rv; } } } void run() throws Exception { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int Q = sc.nextInt(); long[] A = new long[N]; for (int i = 0; i < A.length; ++i) { A[i] = sc.nextLong(); } SegTree seg1 = new SegTree(N); SegTree seg2 = new SegTree(N); for (int i = 0; i < N; ++i) { seg1.v[i + seg1.n - 1] = A[i]; } for (int i = seg1.n - 2; i >= 0; --i) { seg1.v[i] = seg1.v[2 * i + 1] + seg1.v[2 * i + 2]; } for (int i = 0; i < Q; ++i) { int query = sc.nextInt(); int x = sc.nextInt(); --x; if (query == 1) { if (seg2.sum(x, x + 1) == 0) { seg2.add(x, 1); } } else if (query == 2) { if (seg2.sum(x, x + 1) == 1) { seg2.add(x, -1); } } else if (query == 3) { seg1.add(x, 1); } else if (query == 4) { int r_ng = N; int r_ok = x; while (r_ng - r_ok > 1) { int m = (r_ng + r_ok) / 2; if (seg2.sum(x, m) < m - x) { r_ng = m; } else { r_ok = m; } } int l_ok = x;// [x, x) int l_ng = -1; while (l_ok - l_ng > 1) { int m = (l_ng + l_ok) / 2; if (seg2.sum(m, x) < x - m) { l_ng = m; } else { l_ok = m; } } System.out.println(seg1.sum(l_ok, r_ok + 1)); } } } void tr(Object... objects) { System.out.println(Arrays.deepToString(objects)); } }