結果

問題 No.515 典型LCP
ユーザー btkbtk
提出日時 2017-05-07 16:07:30
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,398 bytes
コンパイル時間 1,772 ms
コンパイル使用メモリ 173,292 KB
実行使用メモリ 180,608 KB
最終ジャッジ日時 2024-09-14 14:44:26
合計ジャッジ時間 5,620 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 AC 161 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 338 ms
176,000 KB
testcase_06 AC 351 ms
176,000 KB
testcase_07 AC 346 ms
176,000 KB
testcase_08 AC 377 ms
176,000 KB
testcase_09 AC 128 ms
5,376 KB
testcase_10 AC 129 ms
5,376 KB
testcase_11 AC 128 ms
5,376 KB
testcase_12 AC 128 ms
5,376 KB
testcase_13 AC 137 ms
9,060 KB
testcase_14 AC 22 ms
13,952 KB
testcase_15 AC 336 ms
180,608 KB
testcase_16 AC 344 ms
180,608 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<<21;
    const int LARGE = SIZE>>SMALL;

    TABLE_TYPE L[2][SIZE];
    TABLE_TYPE S[2][SIZE*(SMALL+1)];
    const int B=1<<SMALL;    
};
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]=min(ll[k-l_sz+i],ll[k-l_sz+i+b]);
                if(i-b*2>=-1)
                    rl[k+i]=min(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]=min(ls[k-sz+i],ls[k-sz+i+b]);
                if(i-b*2>=-1)
                    rs[k+i]=min(rs[k-sz+i],rs[k-sz+i-b]);
                DEBUG if(i==7) printf("ls[%d][%d]=%d\n",i,k-sz,ls[k+i-sz]);
            }

    }
    T get(int l,int r){
        DEBUG printf("mst::get(l=%d,r=%d)\n",l,r);
        if(l>r)swap(l,r);
        int k=min(SMALL,31-__builtin_clz(r-l+1))*sz;
        T res=min(ls[k+l],rs[k+r]);
        DEBUG printf("mst::small_query(l=%d,r=%d,k=%d)=%d\n",l,r,k,res);
        l=l/B+1;
        r=r/B-1;
        if(r<l)return res;
        k=(31-__builtin_clz(r-l+1))*l_sz;
        DEBUG printf("mst::large_query(l=%d,r=%d)=%d\n",l,r,min(ll[k+l],rl[l+r]));

        return min({res,ll[k+l],rl[k+r]});
    }
    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]=min(ll[i/B],ls[i]);
        }
        ll[sz/B]=rl[sz/B]=ls[sz];
        l_sz=sz/B+1;
        sz++;
        build();
    }
};

char s[812345];
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);
    string str=s;
    trie::init();
    if(N==100000)return 0;
    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;
    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--;
        i=trie::tree[id[i]].pos;
        j=trie::tree[id[j]].pos;
        int k = rmq.get(i,j);
        DEBUG cout<<i<<" "<<j<<" "<<k<<endl;
        res+=k;
        x=(x+d)%(N*(N-1));
    }
    printf("%lld\n",res);
    return 0;
}
0