結果
問題 | No.1975 Zigzag Sequence |
ユーザー | ks2m |
提出日時 | 2022-06-10 23:16:28 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 730 ms / 2,000 ms |
コード長 | 3,424 bytes |
コンパイル時間 | 2,655 ms |
コンパイル使用メモリ | 88,248 KB |
実行使用メモリ | 70,604 KB |
最終ジャッジ日時 | 2023-10-21 05:42:56 |
合計ジャッジ時間 | 20,447 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 69 ms
53,940 KB |
testcase_01 | AC | 68 ms
51,848 KB |
testcase_02 | AC | 68 ms
53,920 KB |
testcase_03 | AC | 219 ms
59,112 KB |
testcase_04 | AC | 140 ms
55,928 KB |
testcase_05 | AC | 730 ms
69,324 KB |
testcase_06 | AC | 568 ms
67,504 KB |
testcase_07 | AC | 216 ms
59,184 KB |
testcase_08 | AC | 542 ms
65,636 KB |
testcase_09 | AC | 610 ms
69,552 KB |
testcase_10 | AC | 578 ms
67,620 KB |
testcase_11 | AC | 546 ms
67,468 KB |
testcase_12 | AC | 240 ms
57,500 KB |
testcase_13 | AC | 69 ms
54,460 KB |
testcase_14 | AC | 68 ms
54,412 KB |
testcase_15 | AC | 68 ms
54,484 KB |
testcase_16 | AC | 68 ms
54,500 KB |
testcase_17 | AC | 69 ms
54,504 KB |
testcase_18 | AC | 416 ms
68,112 KB |
testcase_19 | AC | 423 ms
67,976 KB |
testcase_20 | AC | 564 ms
68,828 KB |
testcase_21 | AC | 553 ms
68,872 KB |
testcase_22 | AC | 608 ms
68,696 KB |
testcase_23 | AC | 671 ms
70,604 KB |
testcase_24 | AC | 640 ms
68,604 KB |
testcase_25 | AC | 588 ms
68,632 KB |
testcase_26 | AC | 721 ms
69,176 KB |
testcase_27 | AC | 645 ms
68,584 KB |
testcase_28 | AC | 600 ms
68,700 KB |
testcase_29 | AC | 615 ms
68,712 KB |
testcase_30 | AC | 710 ms
68,844 KB |
testcase_31 | AC | 643 ms
68,924 KB |
testcase_32 | AC | 546 ms
68,952 KB |
testcase_33 | AC | 547 ms
68,816 KB |
testcase_34 | AC | 697 ms
68,604 KB |
testcase_35 | AC | 653 ms
68,552 KB |
ソースコード
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.PriorityQueue; import java.util.Queue; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); String[] sa = br.readLine().split(" "); Obj[] arr = new Obj[n]; for (int i = 0; i < n; i++) { Obj o = new Obj(); o.i = i; o.a = Integer.parseInt(sa[i]); arr[i] = o; } br.close(); PriorityQueue<Obj> que1 = new PriorityQueue<>((o1, o2) -> o1.a - o2.a); PriorityQueue<Obj> que2 = new PriorityQueue<>((o1, o2) -> o2.a - o1.a); for (Obj o : arr) { que1.add(o); que2.add(o); } int mod = 1000000007; long[] p = new long[n + 1]; p[0] = 1; for (int i = 1; i < p.length; i++) { p[i] = p[i - 1] * 2 % mod; } long ans = 0; FenwickTree ft1 = new FenwickTree(n); FenwickTree ft2 = new FenwickTree(n); Queue<Obj> que = new ArrayDeque<>(); Obj pre = new Obj(); while (!que1.isEmpty()) { Obj o = que1.poll(); if (o.a != pre.a) { while (!que.isEmpty()) { Obj o2 = que.poll(); ft1.add(o2.i, p[o2.i]); ft2.add(o2.i, p[n - 1 - o2.i]); } } long v1 = ft1.sum(o.i) % mod; long v2 = ft2.sum(o.i + 1, n) % mod; ans += v1 * v2 % mod; ans %= mod; que.add(o); pre = o; } ft1 = new FenwickTree(n); ft2 = new FenwickTree(n); que = new ArrayDeque<>(); pre = new Obj(); while (!que2.isEmpty()) { Obj o = que2.poll(); if (o.a != pre.a) { while (!que.isEmpty()) { Obj o2 = que.poll(); ft1.add(o2.i, p[o2.i]); ft2.add(o2.i, p[n - 1 - o2.i]); } } long v1 = ft1.sum(o.i) % mod; long v2 = ft2.sum(o.i + 1, n) % mod; ans += v1 * v2 % mod; ans %= mod; que.add(o); pre = o; } System.out.println(ans); } static class Obj { int i, a; } } class FenwickTree { private int n; private long[] data; /** * 長さnの配列(a[0]~a[n-1])を作る。初期値は全て0。<br> * O(n) * * @param n 配列の長さ */ public FenwickTree(int n) { this.n = n; data = new long[n]; } /** * 初期データを元にFenwick Treeを構成する。<br> * O(n) * * @param data 初期データ */ public FenwickTree(long[] data) { this(data.length); build(data); } /** * a[p] += x を行う。<br> * O(log n) * * @param p 加算位置(0≦p<n) * @param x 加算値 */ void add(int p, long x) { assert 0 <= p && p < n : "p=" + p; p++; while (p <= n) { data[p - 1] += x; p += p & -p; } } /** * a[l] + ... + a[r-1] を返す。<br> * O(log n) * * @param l 開始位置(含む) (0≦l≦r≦n) * @param r 終了位置(含まない)(0≦l≦r≦n) */ long sum(int l, int r) { assert 0 <= l && l <= r && r <= n : "l=" + l + ", r=" + r; return sum(r) - sum(l); } /** * a[0] + ... + a[r-1] を返す。<br> * O(log n) * * @param r 終了位置(含まない)(0≦r≦n) */ long sum(int r) { assert 0 <= r && r <= n : "r=" + r; long s = 0; while (r > 0) { s += data[r - 1]; r -= r & -r; } return s; } private void build(long[] dat) { System.arraycopy(dat, 0, data, 0, n); for (int i = 1; i <= n; i++) { int p = i + (i & -i); if (p <= n) { data[p - 1] += data[i - 1]; } } } }