結果

問題 No.515 典型LCP
ユーザー sahiyasahiya
提出日時 2023-01-29 21:03:10
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 4,759 bytes
コンパイル時間 2,393 ms
コンパイル使用メモリ 177,504 KB
実行使用メモリ 13,108 KB
最終ジャッジ日時 2024-06-29 16:39:49
合計ジャッジ時間 9,717 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 AC 893 ms
13,024 KB
testcase_02 AC 546 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 284 ms
5,376 KB
testcase_06 AC 417 ms
5,376 KB
testcase_07 AC 350 ms
5,376 KB
testcase_08 AC 460 ms
5,376 KB
testcase_09 AC 122 ms
5,376 KB
testcase_10 AC 133 ms
5,376 KB
testcase_11 AC 132 ms
5,376 KB
testcase_12 AC 130 ms
5,376 KB
testcase_13 AC 105 ms
5,376 KB
testcase_14 AC 5 ms
5,376 KB
testcase_15 AC 139 ms
5,376 KB
testcase_16 AC 150 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")

#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstring>
#include <deque>
#include <forward_list>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define ALL(x) (x).begin(), (x).end()
#define PC(x) __builtin_popcount(x)
#define PCL(x) __builtin_popcountll(x)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template <class T>
bool chmax(T& a, const T& b)
{
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
bool chmin(T& a, const T& b)
{
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
const double PI = 3.14159265358979323846;
const double PI2 = PI * 2.0;
const double EPS = 1E-09;
const ll MOD = 1E+09 + 7; // =998244353;
const ll INFL = 1E18;
const int INFI = 1E09;
const int MAX_N = 2E+05;
struct edge {
    int to, cost, id;
};

ll di[4] = { 0, -1, 0, 1 }, dj[4] = { 1, 0, -1, 0 };

template <typename T>
struct segtree {
    using FX = function<T(T, T)>;
    int n;
    FX fx, gx; // fxは区間更新で使う関数,gxは値の更新で使う関数
    const T ex;
    vector<T> dat;
    segtree(int n_, FX fx_, FX gx_, T ex_)
        : dat(n_ * 4, ex_)
        , fx(fx_)
        , gx(gx_)
        , ex(ex_)
    {
        //簡単のため要素数を2のべき乗に
        n = 1;
        while (n < n_) {
            n *= 2;
        }
    }

    // 全てのデータをaで埋める
    void fill(T a)
    {
        fill_n(dat.begin(), dat.size(), a);
    }

    // k番目(0-indexed)の値を取得
    T at(int k)
    {
        //葉の節点
        k += n - 1;
        return dat[k];
    }

    //点更新
    // k番目(0-indexed)の値をaに変更
    void update(int k, T a)
    {
        //葉の節点
        k += n - 1;
        dat[k] = gx(dat[k], a);
        //登りながら更新
        while (k > 0) {
            k = (k - 1) / 2;
            dat[k] = fx(dat[k * 2 + 1], dat[k * 2 + 2]);
        }
    }

    //構造体の外からクエリを呼ぶときは基本的にこちらを使う
    //[a,b)の最小値を求める
    T query(int a, int b)
    {
        return query_sub(a, b, 0, 0, n);
    }
    //[a,b)の最小値を求める
    // kは節点の番号、l,rはその節点が[l,r)に対応づいていることを示す
    //外からはquery(a, b, 0, 0, n)で呼ぶ
    T query_sub(int a, int b, int k, int l, int r)
    {
        //[a,b)と[l,r)が交差しなければTINF
        if (r <= a || b <= l) {
            return ex;
        }

        //[a,b)が[l,r)を完全に含んでいればこの節点の値を返す
        if (a <= l && r <= b) {
            return dat[k];
        } else {
            //そうでなければ2つの子の最小値
            T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
            T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
            return fx(vl, vr);
        }
    }
};

ll N, M;

pll gen(ll& x, ll d)
{
    ll i = (x / (N - 1)) + 1;
    ll j = (x % (N - 1)) + 1;
    if (i > j)
        swap(i, j);
    else
        j++;
    x = (x + d) % (N * (N - 1));
    return { i, j };
}

ll lcp(string& s, string& t)
{
    ll res = 0;
    for (int i = 0; i < min(s.size(), t.size()); ++i) {
        if (s[i] != t[i]) {
            return res;
        }
        res++;
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;

    vector<string> s(N);

    for (int i = 0; i < N; ++i) {
        cin >> s[i];
    }

    auto t = s;
    sort(ALL(t));

    auto fx = [](ll x1, ll x2) { return min(x1, x2); };
    auto gx = [](ll x1, ll x2) { return x2; };
    ll ex = INFL;
    segtree<ll> seg(N, fx, gx, ex);

    for (int i = 0; i + 1 < N; ++i) {
        seg.update(i, lcp(t[i], t[i + 1]));
    }

    vector<int> indices(N);
    for (int i = 0; i < N; ++i) {
        indices[i] = distance(t.begin(), lower_bound(ALL(t), s[i]));
    }

    ll x, d;
    cin >> M >> x >> d;
    ll ans = 0;
    for (int xx = 0; xx < M; ++xx) {
        auto p = gen(x, d);
        ll a = p.first;
        ll b = p.second;
        a--;
        b--;
        int i = indices[a];
        int j = indices[b];
        if (i == j) {
            ans += t[i].size();
            continue;
        }
        if (i > j)
            swap(i, j);
        ans += seg.query(i, j);
    }

    cout << ans << "\n";

    return 0;
}
0