#172466 (C++17) No.515 典型LCP

• 問題: No.515 典型LCP
• ユーザー: mai
• 提出日時: 2017-05-07 12:15:45
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: RE
• 実行時間: -
• コード長: 5,361 bytes
• コンパイル時間: 3,338 ms
• コンパイル使用メモリ: 222,756 KB
• 実行使用メモリ: 14,720 KB
• 最終ジャッジ日時: 2024-09-14 14:39:44
• 合計ジャッジ時間: 6,225 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	266 ms; 14,592 KB
testcase_01	AC	232 ms; 14,720 KB
testcase_02	RE	-
testcase_03	AC	5 ms; 6,656 KB
testcase_04	AC	4 ms; 6,784 KB
testcase_05	AC	89 ms; 7,680 KB
testcase_06	AC	91 ms; 7,680 KB
testcase_07	AC	89 ms; 7,680 KB
testcase_08	AC	100 ms; 7,680 KB
testcase_09	AC	93 ms; 8,320 KB
testcase_10	AC	92 ms; 8,192 KB
testcase_11	AC	92 ms; 8,064 KB
testcase_12	AC	92 ms; 8,192 KB
testcase_13	AC	92 ms; 7,552 KB
testcase_14	AC	23 ms; 7,296 KB
testcase_15	AC	90 ms; 7,296 KB
testcase_16	AC	90 ms; 7,424 KB

ソースコード

#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include "bits/stdc++.h"

#ifdef WINT_MIN
#define __MAI
#endif

using namespace std;
typedef unsigned int uint;
typedef long long int ll;
typedef unsigned long long int ull;

#define debugv(v) printf("L%d %s => ",__LINE__,#v);for(auto e:v){cout<<e<<" ";}cout<<endl;
#define debugm(m) printf("L%d %s is..\n",__LINE__,#m);for(auto v:m){for(auto e:v){cout<<e<<" ";}cout<<endl;}
#define debuga(m,w) printf("L%d %s is => ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout<<endl;
#define debugaa(m,w,h) printf("L%d %s is..\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[x][y]<<" ";}cout<<endl;}
#define debugaar(m,w,h) printf("L%d %s is..\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[y][x]<<" ";}cout<<endl;}
#define ALL(v) (v).begin(),(v).end()
#define repeat(l) for(auto cnt=0;cnt<(l);++cnt)
#define upto(l,r) for(auto cnt=l;cnt<=r;++cnt)
#define downto(r,l) for(auti cnt=r;cnt>=l;--cnt)
#define BIGINT 0x7FFFFFFF
#define MD 1000000007ll
#define PI 3.1415926535897932384626433832795
void printbit(int u) { if (u == 0)cout << 0; else { int s = 0, k = 0; for (; 0<u; u >>= 1, k++)s = (s << 1) | (u & 1); for (; 0<k--; s >>= 1)cout << (s & 1); } }template<typename T1, typename T2>
    ostream& operator <<(ostream &o, const pair<T1, T2> p) { o << "(" << p.first << ":" << p.second << ")"; return o; }

#define TIME chrono::system_clock::now()
#define MILLISEC(t) (chrono::duration_cast<chrono::milliseconds>(t).count())

namespace {
    std::chrono::system_clock::time_point t;
    void tic() { t = TIME; }
    void toc() { fprintf(stderr, "TIME : %lldms\n", MILLISEC(TIME - t)); }
    std::chrono::system_clock::time_point tle = TIME;
    //#ifdef __MAI
    void safe_tle(int msec) { assert(MILLISEC(TIME - tle) < msec); }
    //#else
    //#define safe_tle(k) ;
    //#endif
}

#ifdef __MAI //_getchar_nolock
#define getchar_unlocked getchar
#endif
namespace {
    class MaiScanner {
    public:
        template<typename T>
        void input_integer(T& var) {
            var = 0;
            T sign = 1;
            int cc = getchar_unlocked();
            for (; cc<'0' || '9'<cc; cc = getchar_unlocked())
                if (cc == '-') sign = -1;
            for (; '0' <= cc&&cc <= '9'; cc = getchar_unlocked())
                var = (var << 3) + (var << 1) + cc - '0';
            var = var*sign;
        }
        inline int c() { return getchar_unlocked(); }
        inline MaiScanner& operator>>(int& var) {
            input_integer<int>(var);
            return *this;
        }
        inline MaiScanner& operator>>(long long& var) {
            input_integer<long long>(var);
            return *this;
        }
    };
}
MaiScanner scanner;


template <typename T>
class sparse_table {
public:
    int size;
    vector<int> log2;
    vector<T> data;
    vector<T> dp;

    sparse_table(int size) :size(size), log2(size), data(size) {

        // for fast calculate log2
        for (int i = 2; i <= size; ++i) {
            log2[i] = log2[i >> 1] + 1;
        }

        dp.resize(size*(log2[size] + 1));
    }

    inline T& operator[](size_t i) {return data[i]; }
    inline T operator[](size_t i)const { return data[i]; }

    void build() {
        int l, i, f, b;
        for (i = 0; i < size; i++) {
            dp[i] = i;
        }
        for (l = 1; (1 << l) <= size; l++) {
            for (i = 0; i + (1 << l) <= size; i++) {
                f = dp[i + size*(l - 1)];
                b = dp[(i + (1 << (l - 1))) + size*(l - 1)];

                dp[i + size*l] = (data[f] <= data[b]) ? f : b; // minimum
            }
        }
    }

    // range [l,r]
    T queryIdx(int l, int r) const {
        int lg = log2[r - l + 1];
        int i1 = dp[l + size*lg];
        int i2 = dp[r - (1 << lg) + 1 + size*lg];

        return (data[i1] <= data[i2]) ? i1 : i2; // minimum
    }
};

inline int lcp(string& s1, string& s2) {
    int s = min(s1.size(), s2.size());
    int i;
    for (i = 0; s1[i] == s2[i] && i < s; ++i) {}
    return i;
}

int width, height;
ll m, n, kei;

string str[100010];

int warp[100010];
int rwarp[100010];

int main() {
    ll x, d;
    ll l, r;
    int c;

    // scanner >> n; scanner.c();
// 
    // repeat(n) {
    //     str[cnt].reserve(400);
    //     while ((c = scanner.c()) != '\n')
    //         str[cnt].push_back(c);
// 
    //     warp[cnt] = cnt;
    // }
    // scanner >> m >> x >> d;
    
    cin >> n; scanner.c();

    repeat(n) {
        cin >> str[cnt];
        warp[cnt] = cnt;
    }
    cin >> m >> x >> d;

    sort(warp, warp + n, [](int l, int r) {return str[l] < str[r]; });

    sparse_table<int> st(n);
    
    fill(ALL(st.data),999999);

    repeat(n - 1) {
        rwarp[warp[cnt]] = cnt;
        st[cnt] = lcp(str[warp[cnt]], str[warp[cnt + 1]]);
    }
    rwarp[warp[n - 1]] = n - 1;

    st.build();

    ll result = 0;
    for (ll k = 1; k <= m; ++k) {
        l = (x / (n - 1));
        r = (x % (n - 1));
        if (l > r)
            swap(l, r);
        else {
            r = r + 1;
        }
        x = (x + d) % (n * (n - 1));

        l = rwarp[l];
        r = rwarp[r];
        if (l > r)
            result += st[st.queryIdx(r, l - 1)];
        else
            result += st[st.queryIdx(l, r - 1)];

    }
    cout << result << endl;
    return 0;
}