結果
問題 | No.515 典型LCP |
ユーザー | nebukuro09 |
提出日時 | 2017-05-08 15:09:32 |
言語 | D (dmd 2.106.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,513 bytes |
コンパイル時間 | 930 ms |
コンパイル使用メモリ | 117,512 KB |
実行使用メモリ | 67,656 KB |
最終ジャッジ日時 | 2023-09-03 13:11:51 |
合計ジャッジ時間 | 5,777 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | TLE | - |
testcase_01 | TLE | - |
testcase_02 | AC | 991 ms
52,388 KB |
testcase_03 | AC | 2 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 516 ms
52,600 KB |
testcase_06 | AC | 633 ms
51,852 KB |
testcase_07 | AC | 594 ms
52,308 KB |
testcase_08 | AC | 654 ms
53,848 KB |
testcase_09 | AC | 724 ms
52,808 KB |
testcase_10 | AC | 923 ms
51,292 KB |
testcase_11 | AC | 922 ms
53,340 KB |
testcase_12 | AC | 924 ms
51,024 KB |
testcase_13 | AC | 537 ms
54,120 KB |
testcase_14 | AC | 13 ms
6,016 KB |
testcase_15 | AC | 248 ms
54,324 KB |
testcase_16 | AC | 262 ms
55,568 KB |
ソースコード
import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop; void main() { auto N = readln.chomp.to!int; auto S = N.iota.map!(i => tuple(readln.chomp, i)).array; auto ttt = readln.split.map!(to!long); auto M = ttt[0].to!int; auto x = ttt[1]; auto d = ttt[2]; auto I = new long[](M); auto J = new long[](M); foreach (k; 0..M) { I[k] = (x / (N - 1)) + 1; J[k] = (x % (N - 1)) + 1; if (I[k] > J[k]) swap(I[k], J[k]); else J[k] += 1; x = (x + d) % (N.to!long * (N.to!long - 1)); } S.sort(); auto D = new int[](N-1); foreach (i; 0..N-1) { foreach (j; 0..min(S[i][0].length, S[i+1][0].length)) { if (S[i][0][j] == S[i+1][0][j]) D[i]++; else break; } } auto rev = new int[](N); foreach (i; 0..N) { rev[S[i][1]] = i; } auto st = new SegmentTree(N-1); foreach (i; 0..N-1) st.update(i, D[i]); long[int][int] mem; long ans = 0; foreach (k; 0..M) { int i = rev[I[k.to!int].to!int - 1]; int j = rev[J[k.to!int].to!int - 1]; if (i > j) swap(i, j); if (i in mem && j in mem[i]) ans += mem[i][j]; ans += st.getmin(i, j-1); } ans.writeln; } class SegmentTree { int[] table; int size; this(int n) { assert(bsr(n) < 29); size = 1 << (bsr(n) + 2); table = new int[](size); fill(table, 1 << 29); } void update(int pos, int num) { return update(pos, num, 0, 0, size/2-1); } void update(int pos, int num, int i, int left, int right) { if (left == right) { table[i] = num; return; } auto mid = (left + right) / 2; if (pos <= mid) update(pos, num, i*2+1, left, mid); else update(pos, num, i*2+2, mid+1, right); table[i] = min(table[i*2+1], table[i*2+2]); } int getmin(int pl, int pr) { return getmin(pl, pr, 0, 0, size/2-1); } int getmin(int pl, int pr, int i, int left, int right) { if (pl > right || pr < left) return 1 << 29; else if (pl <= left && right <= pr) return table[i]; else return min(getmin(pl, pr, i*2+1, left, (left+right)/2), getmin(pl, pr, i*2+2, (left+right)/2+1, right)); } }