제출 #42859

#제출 시각아이디문제언어결과실행 시간메모리
42859ToMoClone회문 (APIO14_palindrome)C++14
컴파일 에러
0 ms0 KiB
/*input www a aba abacaba acaba ba bacaba caba */ #include <bits/stdc++.h> using namespace std; const int N = 300005; namespace SuffixArray { int pos[N], sa[N], tmp[N], lcp[N], gap, n; string s; bool SuffixCmp(int i, int j) { if(pos[i] != pos[j]) return pos[i] < pos[j]; i += gap, j += gap; return (i < n && j < n) ? (pos[i] < pos[j]) : (i > j); } void buildSA(string x) { n = (int)x.size(), s = x; for(int i = 0; i < n; ++i) pos[i] = s[i], sa[i] = i; for(gap = 1; ; gap *= 2) { sort(sa, sa + n, SuffixCmp); for(int i = 1; i < n; ++i) tmp[i] = tmp[i - 1] + SuffixCmp(sa[i - 1], sa[i]); for(int i = 0; i < n; ++i) pos[sa[i]] = tmp[i]; if(tmp[n - 1] == n - 1) break; } } void Kasai() { for(int i = 0, k = 0; i < n; ++i) if(pos[i] != n - 1) { for(int j = sa[pos[i] + 1]; s[i + k] == s[j + k]; ++k); lcp[pos[i]] = k; if(k != 0) --k; } } } namespace MaxRange { int lef[N], rig[N], mn[18][N]; int get(int l, int r) { int dist = log2(r - l + 1); return min(mn[dist][l], mn[dist][r - (1 << dist) + 1]); } int64_t Solve(vector<int> &x, vector<int> &val) { int n = x.size(); for(int i = 1; i < n - 1; ++i) mn[0][i] = x[i]; for(int i = 1; (1 << i) < n - 1; ++i) for(int j = 1; j + (1 << i) < n; ++j) mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + (1 << (i - 1))]); int64_t Ans = 0; for(int i = 1; i < n - 1; ++i) { int le = 1, ri = i - 1, l, r; if(i == 1) l = 1; else if(x[i - 1] < val[i]) l = i; else { while(le < ri) { int mid = (le + ri) >> 1; if(get(mid, i - 1) < val[i]) le = mid + 1; else ri = mid; } l = le; } if(i == n - 2) r = i; else if(x[i] < val[i]) r = i; else { le = i, ri = n - 2; while(le < ri) { int mid = (le + ri + 1) >> 1; if(get(i, mid) < val[i]) ri = mid - 1; else le = mid; } r = le + 1; } Ans = max(Ans, 1ll * (r - l + 1) * val[i]); } return Ans; } } int main(){ string s; cin >> s; int n = (int)s.size(); SuffixArray::buildSA(s); SuffixArray::Kasai(); vector<int> v, val; v.reserve(n + 2), val.reserve(n + 2); v.emplace_back(- 1), val.emplace_back(0); for(int i = 0; i < n; ++i) { v.emplace_back(SuffixArray::lcp[i]); val.emplace_back(n - SuffixArray::sa[i]); } v.emplace_back(- 1), val.emplace_back(0); cout << MaxRange::Solve(v, val) << endl; // cerr << fixed << setprecision(6) << (double)clock() / CLOCKS_PER_SEC << endl; }

컴파일 시 표준 에러 (stderr) 메시지

palindrome.cpp: In function 'int64_t MaxRange::Solve(std::vector<int>&, std::vector<int>&)':
palindrome.cpp:89:45: error: no matching function for call to 'max(int64_t&, long long int)'
    Ans = max(Ans, 1ll * (r - l + 1) * val[i]);
                                             ^
In file included from /usr/include/c++/5/bits/char_traits.h:39:0,
                 from /usr/include/c++/5/ios:40,
                 from /usr/include/c++/5/istream:38,
                 from /usr/include/c++/5/sstream:38,
                 from /usr/include/c++/5/complex:45,
                 from /usr/include/c++/5/ccomplex:38,
                 from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:52,
                 from palindrome.cpp:11:
/usr/include/c++/5/bits/stl_algobase.h:219:5: note: candidate: template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)
     max(const _Tp& __a, const _Tp& __b)
     ^
/usr/include/c++/5/bits/stl_algobase.h:219:5: note:   template argument deduction/substitution failed:
palindrome.cpp:89:45: note:   deduced conflicting types for parameter 'const _Tp' ('long int' and 'long long int')
    Ans = max(Ans, 1ll * (r - l + 1) * val[i]);
                                             ^
In file included from /usr/include/c++/5/bits/char_traits.h:39:0,
                 from /usr/include/c++/5/ios:40,
                 from /usr/include/c++/5/istream:38,
                 from /usr/include/c++/5/sstream:38,
                 from /usr/include/c++/5/complex:45,
                 from /usr/include/c++/5/ccomplex:38,
                 from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:52,
                 from palindrome.cpp:11:
/usr/include/c++/5/bits/stl_algobase.h:265:5: note: candidate: template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)
     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^
/usr/include/c++/5/bits/stl_algobase.h:265:5: note:   template argument deduction/substitution failed:
palindrome.cpp:89:45: note:   deduced conflicting types for parameter 'const _Tp' ('long int' and 'long long int')
    Ans = max(Ans, 1ll * (r - l + 1) * val[i]);
                                             ^
In file included from /usr/include/c++/5/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:64,
                 from palindrome.cpp:11:
/usr/include/c++/5/bits/stl_algo.h:3457:5: note: candidate: template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)
     max(initializer_list<_Tp> __l)
     ^
/usr/include/c++/5/bits/stl_algo.h:3457:5: note:   template argument deduction/substitution failed:
palindrome.cpp:89:45: note:   mismatched types 'std::initializer_list<_Tp>' and 'long int'
    Ans = max(Ans, 1ll * (r - l + 1) * val[i]);
                                             ^
In file included from /usr/include/c++/5/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:64,
                 from palindrome.cpp:11:
/usr/include/c++/5/bits/stl_algo.h:3463:5: note: candidate: template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)
     max(initializer_list<_Tp> __l, _Compare __comp)
     ^
/usr/include/c++/5/bits/stl_algo.h:3463:5: note:   template argument deduction/substitution failed:
palindrome.cpp:89:45: note:   mismatched types 'std::initializer_list<_Tp>' and 'long int'
    Ans = max(Ans, 1ll * (r - l + 1) * val[i]);
                                             ^