結果

問題 No.962 LCPs
コンテスト
ユーザー polylogK
提出日時 2019-12-22 11:40:01
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,013 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 479 ms
コンパイル使用メモリ 67,808 KB
最終ジャッジ日時 2026-04-04 09:27:16
合計ジャッジ時間 2,226 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge4_0
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:5:18: error: 'int_fast64_t' in namespace 'std' does not name a type
    5 | using i64 = std::int_fast64_t;
      |                  ^~~~~~~~~~~~
main.cpp: In function 'int main()':
main.cpp:14:21: error: 'i64' was not declared in this scope
   14 |         std::vector<i64> a(n - 1);
      |                     ^~~
main.cpp:14:24: error: template argument 1 is invalid
   14 |         std::vector<i64> a(n - 1);
      |                        ^
main.cpp:14:24: error: template argument 2 is invalid
main.cpp:19:26: error: invalid types 'int[int]' for array subscript
   19 |                         a[i] = j + 1;
      |                          ^
main.cpp:23:12: error: expected ';' before 'ans'
   23 |         i64 ans = 0;
      |            ^~~~
      |            ;
main.cpp:24:24: error: 'ans' was not declared in this scope; did you mean 'abs'?
   24 |         for(auto v: s) ans += v.size();
      |                        ^~~
      |                        abs
main.cpp:26:32: error: request for member 'size' in 'a', which is of non-class type 'int'
   26 |         std::vector<int> nxt(a.size());
      |                                ^~~~
main.cpp:27:28: error: request for member 'size' in 'a', which is of non-class type 'int'
   27 |         for(int i = (int)a.size() - 1; i >= 0; i--) {
      |                            ^~~~
main.cpp:29:31: error: request for member 'size' in 'a', which is of non-class type 'int'
   29 |                 while(now < a.size()) {
      |                               ^~~~
main.cpp:30:29: error: invalid types 'int[int]' for array subscript
   30 |                         if(a[now] < a[i]) break;
      |                             ^
main.cpp:30:38: error: invalid types 'int[int]' for array subscript
   30 |                         if(a[now] < a[i]) break;
      |                                      ^
main.cpp:36:30: error: request for member 'size' in 'a', which is of non-class type 'int'
   36 |         for(int i = 0; i < a.siz

ソースコード

diff #
raw source code 

#include <vector>
#include <iostream>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using i64 = std::int_fast64_t;

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

	int n; std::cin >> n; std::vector<std::string> s(n);
	for(int i = 0; i < n; i++) std::cin >> s[i];

	std::vector<i64> a(n - 1);
	for(int i = 0; i < n - 1; i++) {
		for(int j = 0; j < std::min(s[i + 1].size(), s[i].size()); j++) {
			if(s[i][j] != s[i + 1][j]) break;

			a[i] = j + 1;
		}
	}

	i64 ans = 0;
	for(auto v: s) ans += v.size();

	std::vector<int> nxt(a.size());
	for(int i = (int)a.size() - 1; i >= 0; i--) {
		int now = i + 1;
		while(now < a.size()) {
			if(a[now] < a[i]) break;
			now = nxt[now];
		}
		nxt[i] = now;
	}

	for(int i = 0; i < a.size(); i++) {
		int now = i;
		while(now < a.size() and a[now]) {
			i64 S = now - i + 2, T = nxt[now] - i + 1;
			i64 len = (S + T) * (T - S + 1) >> 1;

			ans += len * a[now];
			now = nxt[now];
		}
	}

	printf("%lld\n", ans);
	return 0;
}
0