結果
問題 |
No.962 LCPs
|
ユーザー |
![]() |
提出日時 | 2020-01-13 03:55:36 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 22 ms / 2,000 ms |
コード長 | 3,206 bytes |
コンパイル時間 | 1,763 ms |
コンパイル使用メモリ | 180,436 KB |
実行使用メモリ | 9,328 KB |
最終ジャッジ日時 | 2024-12-14 13:22:53 |
合計ジャッジ時間 | 5,083 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 64 |
ソースコード
// #define DEBUGGING #include <bits/stdc++.h> #define endl '\n' #define ALL(V) (V).begin(), (V).end() #define ALLR(V) (V).rbegin(), (V).rend() template <typename T> using V = std::vector<T>; template <typename T> using VV = V<V<T>>; using ll = std::int64_t; using ull = std::uint64_t; using PLL = std::pair<ll, ll>; using TLL = std::tuple<ll, ll, ll>; template <typename T> const T& var_min(const T &t) { return t; } template <typename T> const T& var_max(const T &t) { return t; } template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return std::min(t, var_min(tail...)); } template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return std::max(t, var_max(tail...)); } template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); } template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); } template <typename T> const T& clamp(const T &t, const T &low, const T &high) { return std::max(low, std::min(high, t)); } template <typename T> void chclamp(T &t, const T &low, const T &high) { return t = clamp(t, low, high); } namespace init__ { struct InitIO { InitIO() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << std::fixed << std::setprecision(30); } } init_io; } #define mv_rec make_v(init, tail...) template <typename T> T make_v(T init) { return init; } template <typename T, typename... Tail> auto make_v(T init, size_t s, Tail... tail) { return V<decltype(mv_rec)>(s, mv_rec); } #undef mv_rec using namespace std; #ifdef DEBUGGING #include "../../debug/debug.cpp" #else #define DEBUG(...) 0 #define DEBUG_SEPARATOR_LINE 0 #endif ll sum1(ll n) { return n * (n + 1) / 2; } ll sum2(ll n) { return n * (n + 1) * (2 * n + 1) / 6; } int main() { ll N; cin >> N; V<string> vs(N); for (auto &&s : vs) cin >> s; queue<PLL> rq; rq.emplace(0, N); ll ans = 0; ll idx = 0; for (ll idx = 0; rq.size(); idx++) { queue<PLL> nrq; while (rq.size()) { ll l, r; tie(l, r) = rq.front(); rq.pop(); V<PLL> rngs; // remove vs[i].size() <= idx ll cl = -1; for (ll i = l; i <= r; i++) { ll len = (i == r ? -1 : vs[i].size()); if (len <= idx && cl != -1) { rngs.emplace_back(cl, i); cl = -1; } else if (idx < len && cl == -1) { cl = i; } } for (PLL p : rngs) { ll l, r; tie(l, r) = p; ll cl = l; char cur = vs[l][idx]; for (ll i = l + 1; i <= r; i++) { char nxt = (i == r ? 0 : vs[i][idx]); if (cur == nxt) continue; ll len = i - cl; ans += (len + 1) * sum1(len) - sum2(len); nrq.emplace(cl, i); cl = i; cur = nxt; } } } rq = move(nrq); } cout << ans << endl; return 0; }