結果

問題 No.515 典型LCP
ユーザー btkbtk
提出日時 2017-05-07 17:17:10
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 598 ms / 1,000 ms
コード長 4,260 bytes
コンパイル時間 1,930 ms
コンパイル使用メモリ 173,020 KB
実行使用メモリ 180,736 KB
最終ジャッジ日時 2024-09-14 14:49:56
合計ジャッジ時間 6,432 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge6
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 598 ms
113,536 KB
testcase_01 AC 128 ms
5,376 KB
testcase_02 AC 117 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 3 ms
5,376 KB
testcase_05 AC 300 ms
176,000 KB
testcase_06 AC 225 ms
176,000 KB
testcase_07 AC 217 ms
176,128 KB
testcase_08 AC 230 ms
176,000 KB
testcase_09 AC 85 ms
5,376 KB
testcase_10 AC 85 ms
5,504 KB
testcase_11 AC 84 ms
5,376 KB
testcase_12 AC 85 ms
5,376 KB
testcase_13 AC 93 ms
9,088 KB
testcase_14 AC 21 ms
13,952 KB
testcase_15 AC 212 ms
180,608 KB
testcase_16 AC 214 ms
180,736 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;


#define fin "\n"
#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
#define pb push_back
#define DEBUG if(0)
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l,T r)
{bool a=l>r;if(a)l=r;return a;}
template <typename T>inline bool chmax(T &l,T r)
{bool a=l<r;if(a)l=r;return a;}
template <typename T>
istream& operator>>(istream &is,vector<T> &v){
    for(auto &it:v)is>>it;
    return is;
}
typedef int TABLE_TYPE;
const int SMALL = 5;

namespace TABLE{
    /*
      s=2^SMALL
      l=MAX_SIZE/SMALL
     */
    const int SIZE = 1<<22;
    const int LARGE = SIZE>>SMALL;

    TABLE_TYPE L[2][SIZE];
    TABLE_TYPE S[2][SIZE*(SMALL+1)];
    const int B=1<<SMALL;    
};
#define btk(a,b) (a<b?a:b)
struct min_sparse_table{
    using T=TABLE_TYPE;
    T *ll,*rl;
    T *ls,*rs;
    int sz;
    int l_sz;
    int B;
    void build(){
        for(int k = l_sz,b=1 ;b*2<=l_sz; k+=l_sz,b<<=1)
            REP(i,l_sz){
                if(i+b*2<=l_sz)
                    ll[k+i]=btk(ll[k-l_sz+i],ll[k-l_sz+i+b]);
                if(i-b*2>=-1)
                    rl[k+i]=btk(rl[k-l_sz+i],rl[k-l_sz+i-b]);
            }
        for(int k = sz,b=1,r=0 ;b*2<=sz&&b<(1<<SMALL); k+=sz,b<<=1)
            REP(i,sz){
                if(i+b*2<=sz)
                    ls[k+i]=btk(ls[k-sz+i],ls[k-sz+i+b]);
                if(i-b*2>=-1)
                    rs[k+i]=btk(rs[k-sz+i],rs[k-sz+i-b]);
            }

    }
    T get(int l,int r){

        if(l>r)swap(l,r);
        int k=btk(SMALL,31-__builtin_clz(r-l+1))*sz;
        T res=btk(ls[k+l],rs[k+r]);
        l=l/B+1;
        r=r/B-1;
        if(r<l)return res;
        k=(31-__builtin_clz(r-l+1))*l_sz;
        T ans=btk(ll[k+l],rl[k+r]);
        return btk(res,ans);
    }
    min_sparse_table(std::vector<T> &v)
        :ll(TABLE::L[0]),
         rl(TABLE::L[1]),
         ls(TABLE::S[0]),
         rs(TABLE::S[1]){
        sz=v.size();
        B=TABLE::B;
        ls[0]=rs[0]=0;
        REP(i,sz){
            ls[i+1]=rs[i+1]=ls[i]+v[i];
            if(i%B==0)ll[i/B]=rl[i/B]=ls[i];
            else ll[i/B]=rl[i/B]=btk(ll[i/B],ls[i]);
        }
        ll[sz/B]=rl[sz/B]=btk(ll[sz/B],ls[sz]);
        l_sz=sz/B+1;
        sz++;
        build();
    }
};

char s[912345];
typedef vector<int> V;
V input(int N){
    char *ss=s;
    vector<int> id(N+1);
    int len=0;
    REP(i,N){
        scanf("%s",ss);
        id[i]=len;
        while(*ss !='\0'){
            ss++;len++;
        }
        *(ss++)='\0';len++;
    }
    id.back()=len;
    *(ss++)='\0';
    return id;
}
struct node{
    int nxt[26];
    int pos;
};
namespace trie{
    const int  SZ = 812345;
    node tree[SZ];
    int sz=0;
    int add_node(){
        REP(j,26)tree[sz].nxt[j]=-1;
        return sz++;
    }
    void init(){
        add_node();
    }
    int insert(char* p){
        int now=0;
        while(*p!='\0'){
            int &nxt=tree[now].nxt[(*p)-'a'];
            if(nxt==-1)nxt=add_node();
            now=nxt;
            p++;
        }
        return now;
    }
    void dfs(int v,V &seq){
        tree[v].pos=seq.size();
        REP(i,26)if(tree[v].nxt[i]!=-1){
            seq.pb(+1);
            dfs(tree[v].nxt[i],seq);
            seq.pb(-1);
        }
    }
    V get_seq(){
        V seq;
        seq.reserve(2*sz+10);
        dfs(0,seq);
        return seq;
    }
}

int main(){
    int N;
    scanf("%d",&N);
    auto id = input(N);
    auto pp=id;
    string str=s;
    trie::init();
    REP(i,N)id[i]=trie::insert(s+id[i]);
    LL x,d,M;
    scanf("%lld %lld %lld",&M,&x,&d);
    auto seq=trie::get_seq();
    min_sparse_table rmq(seq);
    LL res=0;
    const LL camy=N*(N-1ll);
    d%=camy;
    REP(q,M){
        LL i = x/(N-1)+1;
        LL j = x%(N-1)+1;
        if(i>j)swap(i,j);
        else j++;
        i--,j--;
        //if(s[pp[i]]==s[pp[j]]){
            i=trie::tree[id[i]].pos;
            j=trie::tree[id[j]].pos;
            
            int k = rmq.get(i,j);
            res+=k;
            //}
        x=(x+d);
        if(x>=camy)x-=camy;
    }
    printf("%lld\n",res);
    return 0;
}
0