結果

問題 No.962 LCPs
コンテスト
ユーザー polylogK
提出日時 2019-12-22 11:39:12
言語 C++17(clang)
(clang++ 22.1.2 + boost 1.89.0)
コンパイル:
clang++ -O2 -lm -std=c++1z -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 946 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 391 ms
コンパイル使用メモリ 108,388 KB
最終ジャッジ日時 2026-05-24 06:55:00
合計ジャッジ時間 1,261 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:3:13: error: no type named 'int_fast64_t' in namespace 'std'; did you mean '__int_least64_t'?
    3 | using i64 = std::int_fast64_t;
      |             ^~~~~~~~~~~~~~~~~
      |             __int_least64_t
/usr/include/x86_64-linux-gnu/bits/types.h:58:19: note: '__int_least64_t' declared here
   58 | typedef __int64_t __int_least64_t;
      |                   ^
main.cpp:12:14: error: use of undeclared identifier 'i64'
   12 |         std::vector<i64> a(n - 1);
      |                     ^~~
main.cpp:21:2: error: unknown type name 'i64'
   21 |         i64 ans = 0;
      |         ^
main.cpp:37:4: error: unknown type name 'i64'
   37 |                         i64 S = now - i + 2, T = nxt[now] - i + 1;
      |                         ^
main.cpp:37:26: error: expected ';' at end of declaration
   37 |                         i64 S = now - i + 2, T = nxt[now] - i + 1;
      |                                               ^
      |                                               ;
main.cpp:38:4: error: unknown type name 'i64'
   38 |                         i64 len = (S + T) * (T - S + 1) >> 1;
      |                         ^
main.cpp:38:19: error: use of undeclared identifier 'T'
   38 |                         i64 len = (S + T) * (T - S + 1) >> 1;
      |                                        ^
main.cpp:38:25: error: use of undeclared identifier 'T'
   38 |                         i64 len = (S + T) * (T - S + 1) >> 1;
      |                                              ^
8 errors generated.

ソースコード

diff #
raw source code 

#include <vector>
#include <iostream>
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