結果
問題 | No.515 典型LCP |
ユーザー |
![]() |
提出日時 | 2017-04-05 01:16:32 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,004 bytes |
コンパイル時間 | 2,198 ms |
コンパイル使用メモリ | 168,384 KB |
実行使用メモリ | 53,500 KB |
最終ジャッジ日時 | 2024-09-14 09:52:37 |
合計ジャッジ時間 | 11,425 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 13 TLE * 2 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long int64;const int INF = 1 << 30;struct SegmentTree{vector< int > seg;int sz;SegmentTree(int n){sz = 1;while(sz < n) sz <<= 1;seg.assign(2 * sz - 1, INF);}void set(int k, int x){seg[k + sz - 1] = x;}void build(){for(int k = sz - 2; k >= 0; k--) {seg[k] = min(seg[2 * k + 1], seg[2 * k + 2]);}}int rmq(int a, int b, int k, int l, int r){if(a >= r || b <= l) return (INF);if(a <= l && r <= b) return (seg[k]);return (min(rmq(a, b, 2 * k + 1, l, (l + r) >> 1),rmq(a, b, 2 * k + 2, (l + r) >> 1, r)));}int rmq(int a, int b){return (rmq(a, b, 0, 0, sz));}void update(int k, int x){k += sz - 1;seg[k] = x;while(k > 0) {k = (k - 1) >> 1;seg[k] = min(seg[2 * k + 1], seg[2 * k + 2]);}}};int N, M;int64 x, d;string S[800000];int latte[3000000], malta[3000000];int main(){cin >> N;int all = 0;for(int i = 0; i < N; i++) {cin >> S[i];all += S[i].size();}cin >> M >> x >> d;for(int k = 0; k < M; k++) {latte[k] = (x / (N - 1)) + 1;malta[k] = (x % (N - 1)) + 1;if(latte[k] > malta[k]) swap(latte[k], malta[k]);else malta[k] = malta[k] + 1;x = (x + d) % (1LL * N * (N - 1));}vector< int > order(N), rev(N);iota(begin(order), end(order), 0);sort(begin(order), end(order), [&](int a, int b){return (S[a] < S[b]);});for(int i = 0; i < N; i++) rev[order[i]] = i;SegmentTree rmq(N);for(int i = 1; i < N; i++) {int tail = 0, sz = min(S[order[i - 1]].size(), S[order[i]].size());while(tail < sz && S[order[i - 1]][tail] == S[order[i]][tail]) ++tail;rmq.set(i - 1, tail);}rmq.build();int64 ret = 0;for(int i = 0; i < M; i++) {auto get = minmax(rev[--latte[i]], rev[--malta[i]]);ret += rmq.rmq(get.first, get.second);}cout << ret << endl;}