結果

問題 No.515 典型LCP
コンテスト
ユーザー nebukuro09
提出日時 2017-05-11 09:54:35
言語 D
(dmd 2.109.1)
結果
TLE  
実行時間 -
コード長 2,305 bytes
コンパイル時間 970 ms
コンパイル使用メモリ 131,080 KB
実行使用メモリ 268,280 KB
最終ジャッジ日時 2024-06-12 19:08:27
合計ジャッジ時間 5,635 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

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 int[](M);
    auto J = new int[](M);
    foreach (k; 0..M) {
        I[k] = ((x / (N - 1)) + 1).to!int;
        J[k] = ((x % (N - 1)) + 1).to!int;
        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 rev = new int[](N);
    foreach (i; 0..N) {
        rev[S[i][1]] = i;
    }


    auto T = new string[](N);
    foreach (i; 0..N) T[i] = S[i][0];
    auto D = new int[](N-1);
    foreach (i; 0..N-1) {
        foreach (j; 0..min(T[i].length, T[i+1].length)) {
            if (T[i][j] == T[i+1][j]) D[i]++;
            else break;
        }
    }

    auto st = new SparseTable(D);

    long[int][int] mem;
    long ans = 0;
    foreach (k; 0..M.to!int) {
        int i = rev[I[k] - 1];
        int j = rev[J[k] - 1];
        if (i > j) swap(i, j);
        if (i in mem && j in mem[i]) ans += mem[i][j];
        else ans += mem[i][j] = st.getmin(i, j-1);
    }

    ans.writeln;
}

class SparseTable {
    int LOGMAXN = 25;
    int N;
    int[] A;
    int[][] M;
    
    this(int[] A) {
        this.A = A.dup;
        N = A.length.to!int;
        M = new int[][](N, LOGMAXN);
   
        //initialize M for the intervals with length 1
        for (int i = 0; i < N; i++)
            M[i][0] = i;
        //compute values from smaller to bigger intervals
        for (int j = 1; 1 << j <= N; j++)
            for (int i = 0; i + (1 << j) - 1 < N; i++)
                if (A[M[i][j - 1]] < A[M[i + (1 << (j - 1))][j - 1]])
                    M[i][j] = M[i][j - 1];
                else
                    M[i][j] = M[i + (1 << (j - 1))][j - 1];
    }

    int getmin(int i, int j) {
        //int m = j - i + 1;
        int k = bsr(j - i + 1);
        //while (m >>= 1) k += 1;
        int h = A[M[i][k]] <= A[M[j-2^^k+1][k]] ? M[i][k] : M[j-2^^k+1][k];
        return A[h];
    }    
}
0