結果

問題 No.962 LCPs
ユーザー ianCKianCK
提出日時 2019-12-27 06:39:08
言語 C++11
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,185 bytes
コンパイル時間 520 ms
コンパイル使用メモリ 58,720 KB
実行使用メモリ 35,072 KB
最終ジャッジ日時 2024-10-06 17:11:33
合計ジャッジ時間 3,709 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 1 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 1 ms
5,248 KB
testcase_07 WA -
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 1 ms
5,248 KB
testcase_10 AC 1 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 1 ms
5,248 KB
testcase_13 AC 2 ms
5,248 KB
testcase_14 AC 2 ms
5,248 KB
testcase_15 AC 2 ms
5,248 KB
testcase_16 AC 1 ms
5,248 KB
testcase_17 AC 70 ms
35,072 KB
testcase_18 AC 36 ms
19,328 KB
testcase_19 AC 35 ms
19,456 KB
testcase_20 AC 26 ms
15,360 KB
testcase_21 AC 25 ms
15,360 KB
testcase_22 AC 21 ms
11,520 KB
testcase_23 AC 20 ms
11,392 KB
testcase_24 AC 18 ms
10,368 KB
testcase_25 AC 17 ms
10,240 KB
testcase_26 AC 14 ms
9,600 KB
testcase_27 WA -
testcase_28 AC 16 ms
7,808 KB
testcase_29 WA -
testcase_30 AC 19 ms
10,752 KB
testcase_31 WA -
testcase_32 AC 14 ms
6,912 KB
testcase_33 AC 34 ms
18,688 KB
testcase_34 AC 17 ms
8,960 KB
testcase_35 WA -
testcase_36 AC 18 ms
8,448 KB
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 WA -
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
testcase_47 AC 4 ms
5,248 KB
testcase_48 AC 4 ms
5,248 KB
testcase_49 AC 5 ms
5,248 KB
testcase_50 AC 4 ms
5,248 KB
testcase_51 AC 4 ms
5,248 KB
testcase_52 AC 3 ms
5,248 KB
testcase_53 AC 4 ms
5,248 KB
testcase_54 AC 4 ms
5,248 KB
testcase_55 AC 3 ms
5,248 KB
testcase_56 AC 5 ms
5,248 KB
testcase_57 AC 4 ms
5,248 KB
testcase_58 AC 4 ms
5,248 KB
testcase_59 AC 4 ms
5,248 KB
testcase_60 AC 5 ms
5,248 KB
testcase_61 AC 5 ms
5,248 KB
testcase_62 AC 5 ms
5,248 KB
testcase_63 AC 58 ms
22,400 KB
testcase_64 AC 4 ms
5,248 KB
testcase_65 AC 62 ms
22,400 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

bool debug = false;
#include <iostream>
#include <utility>
using namespace std;

#define F first
#define S second

constexpr int kN = int(4E5 + 10), kInf = int(1E9 + 10);

struct seg_tree {
	pair<int, int> p[kN << 2];
	void pull(int n) {
		if (p[(n << 1) + 1].F < p[(n << 1) + 2].F) p[n] = p[(n << 1) + 1];
		else p[n] = p[(n << 1) + 2];
		return ;
	}
	void init(int n, int l, int r, int a[]) {
		if (l == r) p[n] = {a[l], l};
		else {
			int mid = (l + r) >> 1;
			init((n << 1) + 1, l, mid, a);
			init((n << 1) + 2, mid + 1, r, a);
			pull(n);
		}
		return ;
	}
	pair<int, int> ask(int n, int l, int r, int L, int R) {
		if (L <= l && r <= R) return p[n];
		else if (l > R || L > r) return {kInf, l};
		else {
			int mid = (l + r) >> 1;
			pair<int, int> lans = ask((n << 1) + 1, l, mid, L, R), rans = ask((n << 1) + 2, mid + 1, r, L, R);
			if (lans.F < rans.F) return lans;
			else return rans;
		}
	}
};

int LCP(string &a, string &b) {
	int sz = min(int(a.size()), int(b.size()));
	for (int i = 0; i < sz; i++) if (a[i] != b[i]) return i;
	return sz;
}

seg_tree sg;
int a[kN], tot;

long long int dp(int l, int r) {
	if (l > r) return 0;
	pair<int, int> tmp = sg.ask(0, 1, tot, l, r);
	long long int fl, fr, L, R, ans = 0;
	if (!(tmp.S & 1)) L = tmp.S - 1, R = tmp.S + 1;
	else L = R = tmp.S;
	if (debug) printf("l = %d, r = %d, tmp = (%d, %d), L = %lld, R = %lld, ", l, r, tmp.F, tmp.S, L, R);
	if (debug) printf("ans = %lld\n", ((r - R) / 2 + 1) * ((L - l) / 2 + 1) * tmp.F); 
	fl = l >> 1;
	fr = r >> 1;
	L >>= 1;
	R >>= 1;
	ans += (L - fl + 1) * (R + fr) * (fr - R + 1) / 2;
	ans -= (L + fl) * (L - fl + 1) / 2;
	ans += (long long int) (fr - R + 1) * (L - fl + 1);
	if (tmp.S & 1) return ans * tmp.F + dp(l, tmp.S - 2) + dp(tmp.S + 2, r);
	return ans * tmp.F + dp(l, tmp.S - 1) + dp(tmp.S + 1, r);
}

int main() {
	int n;
	string s[2];
	cin >> n >> s[1];
	a[1] = int(s[1].size());
	for (int i = 2; i <= n; i++) {
		cin >> s[i & 1];
		a[(i << 1) - 2] = LCP(s[0], s[1]);
		a[(i << 1) - 1] = int(s[i & 1].size());
	}
	tot = (n << 1) - 1;
	sg.init(0, 1, tot, a);
	printf("%lld\n", dp(1, tot));
}
0