結果

問題 No.515 典型LCP
コンテスト
ユーザー tossy
提出日時 2017-11-17 22:35:28
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 178 ms / 1,000 ms
コード長 2,353 bytes
コンパイル時間 1,573 ms
コンパイル使用メモリ 178,896 KB
実行使用メモリ 20,908 KB
最終ジャッジ日時 2024-11-25 08:53:51
合計ジャッジ時間 4,166 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

template<typename T>
class SparseTable {
public:
  vector<T> tbl[20];
  vector<T> tbr[20];
  int n;
  SparseTable(const vector<T> &v){
    // build table O(NlogN)
    n = v.size();
    tbl[0].resize(n+1);
    tbr[0].resize(n+1);
    rep(i,n) tbl[0][i] = tbr[0][i] = v[i];
    for(int k=1; (1<<k)<=n; k++){
      tbl[k].resize(n+1); tbr[k].resize(n+1);
      int mask = (1<<k)-1;
      rep(i,n){
        if((i&mask) == 0) tbr[k][i] = v[i];
        else tbr[k][i] = min(tbr[k][i-1], v[i]);
      }
      for(int i=n-1; i>=0; i--){
        if(((i+1)&mask) == 0) tbl[k][i] = v[i];
        else tbl[k][i] = min(tbl[k][i+1], v[i]);
      }
    }
  }
  T query(int l, int r){ // [l,r)
    if(l+1 == r) return tbl[0][l];
    r--; // [l,r]
    int k = 31 - __builtin_clz(l^r); // 2^k <= l^r < 2^{k+1}
    return min(tbl[k][l], tbr[k][r]);
  }
};

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  long n;
  cin>>n;
  vector<string> v(n);
  rep(i,n) cin>>v[i];
  vector<int> id(n);
  rep(i,n) id[i] = i;
  sort(all(id), [&](const int l, const int r){
    return v[l] < v[r];
  });

  auto lcp = [&](int p, int q){
    rep(i,min(v[p].size(), v[q].size())) if(v[p][i]!=v[q][i]) return i;
    return (int)min(v[p].size(), v[q].size());
  };

  // lcp btw i,i+1
  vector<int> lcp_arr(n,0);
  rep(i,n-1){
    lcp_arr[i] = lcp(id[i], id[i+1]);
  }
// dbg(lcp_arr);
  SparseTable<int> st(lcp_arr);
  vector<int> pos(n);
  rep(i,n) pos[id[i]] = i;

  long m,x,d;
  cin>>m>>x>>d;

  long ans = 0;
  rep(_,m){
    long i = (x/(n-1));
    long j = (x%(n-1));
    if(i<=j) j++;

    int l = min(pos[i], pos[j]), r = max(pos[i], pos[j]);

    ans += st.query(l, r);
    // dbg(st.query(l,r));
    x = (x+d)%(n*(n-1));
  }

  cout << ans << endl;

  return 0;
}
0