結果
問題 |
No.962 LCPs
|
ユーザー |
![]() |
提出日時 | 2019-12-26 00:12:28 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 15 ms / 2,000 ms |
コード長 | 2,627 bytes |
コンパイル時間 | 1,927 ms |
コンパイル使用メモリ | 176,668 KB |
実行使用メモリ | 10,328 KB |
最終ジャッジ日時 | 2024-10-01 13:04:42 |
合計ジャッジ時間 | 4,857 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 64 |
コンパイルメッセージ
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:64, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/string:50, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/locale_classes.h:40, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/ios_base.h:41, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ios:42, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/istream:38, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/sstream:38, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/complex:45, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ccomplex:39, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/x86_64-pc-linux-gnu/bits/stdc++.h:54, from main.cpp:7: In constructor 'constexpr std::pair<_T1, _T2>::pair(_U1&&, _U2&&) [with _U1 = long long int&; _U2 = int&; typename std::enable_if<(std::_PCC<true, _T1, _T2>::_MoveConstructiblePair<_U1, _U2>() && std::_PCC<true, _T1, _T2>::_ImplicitlyMoveConvertiblePair<_U1, _U2>()), bool>::type <anonymous> = true; _T1 = long long int; _T2 = long long int]', inlined from 'void std::__new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = std::pair<long long int, long long int>; _Args = {long long int&, int&}; _Tp = std::pair<long long int, long long int>]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/new_allocator.h:175:4, inlined from 'static void std::allocator_traits<std::allocator<_CharT> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = std::pair<long long int, long long int>; _Args = {long long int&, int&}; _Tp = std::pair<long long int, long long int>]' at /home/linuxbrew/.linuxbrew/Cel
ソースコード
/** * code generated by JHelper * More info: https://github.com/AlexeyDmitriev/JHelper * @author aajisaka */ #include<bits/stdc++.h> using namespace std; void debug_out() { cerr << endl; } template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #else #define debug(...) 42 #endif #define SPEED ios_base::sync_with_stdio(false);cin.tie(nullptr) #define rep(i,n) for(int i=0; i<(int)(n); i++) #define all(v) v.begin(), v.end() template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } using ll = long long; using P = pair<ll, ll>; constexpr double PI = 3.14159265358979323846; mt19937_64 engine(chrono::steady_clock::now().time_since_epoch().count()); class LCPs { public: void solve(istream& cin, ostream& cout) { SPEED; int n; cin >> n; vector<string> vec(n); ll ans = 0; rep(i, n) { cin >> vec[i]; ans += vec[i].size(); } vector<int> d(n); rep(i, n-1) { int j=0; while(j<vec[i].size() && j<vec[i+1].size() && vec[i][j] == vec[i+1][j]) { j++; } d[i] = j; } stack<P> st; rep(i, n) { if (st.empty() || st.top().second < d[i]) { st.emplace(i, d[i]); } else if (st.top().second == d[i]) { continue; } else { ll pf; while(!st.empty() && st.top().second > d[i]) { auto p = st.top(); st.pop(); ll low = d[i]; if (!st.empty()) chmax(low, st.top().second); ll k = p.second - low; ll r = i - p.first; pf = p.first; debug(k, r); ll now = r*(r+1)*(r+5)/6*k; ans += now; // k, r // (r+1) + r*2 + (r-1)*3 + ... + 2*r // r = 1 -> 2*1 = 2 // r = 2 -> 3*1 + 2*2 = 7 // r = 3 -> 4*1 + 3*2 + 2*3 = 16 // r = 4 -> 5*1 + 4*2 + 3*3 + 2*4 = 30 // r = 5 -> 6*1 + 5*2 + 4*3 + 3*4 + 2*5 = 50 // r = r -> r*(r+1)*(r+5)/6; } if (st.empty() || st.top().second < d[i]) { if (d[i] != 0) st.emplace(pf, d[i]); } } } cout << ans << endl; } }; signed main() { LCPs solver; std::istream& in(std::cin); std::ostream& out(std::cout); solver.solve(in, out); return 0; }