Submission #51975

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
51975	2018-06-22T19:36:02 Z	Milki	Palinilap (COI16_palinilap)	C++14	Compilation error	0 ms	0 KB

palinilap

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cerr << #x << " = " << x << endl
#define _ << " " <<

typedef long long ll;
typedef pair<int, int> point;

const ll MAXN = 1e5 + 5;
const ll MOD = 1e9 + 7;
const ll BAZA = 1307;

string s;
int h[MAXN], h_[MAXN], pot[MAXN];

void calcHash(){
    pot[0] = 1;
    h[0] = s[0];

    FOR(i, 1, (int)s.size()){
        h[i] = ((ll)h[i - 1] * BAZA + s[i]) % MOD;
        pot[i] = (ll)pot[i - 1] * BAZA % MOD;
    }

    h_[0] = s[s.size() - 1];
    for(int i = s.size() - 2, cnt = 1; i >= 0; --i, ++cnt)
        h_[cnt] = ((ll)h_[cnt - 1] * BAZA + s[i]) % MOD;
}

ll calc(ll x, ll y){
    ll k = 0;
    if(x) k = (ll)h[x - 1] * pot[y] % MOD;
    return ((((ll)h[x + y - 1] - k) % MOD) + MOD) % MOD;
}

ll calc_(ll x, ll y){
    ll k = 0;
    if(x) k = (ll)h_[x - 1] * pot[y] % MOD;
    return ((((ll)h_[x + y - 1] - k) % MOD) + MOD) % MOD;
}

ll cntDec[MAXN];
ll decrease[MAXN];
ll increase[MAXN], letInc[MAXN][30];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0),

    cin >> s;

    calcHash();
    ll sol = 0;

    int len = s.size();

    REP(i, len){
        //neparni
        ll lo = 1, hi = min(i + 1, len - i);
        while(lo < hi){
            ll mid = (lo + hi + 1) >> 1;
            /*if(i + mid - 1 >= s.size() || len - i - 1 + mid - 1 >= s.size()){
                assert(s.size() == 0);
            }*/

            if(calc(i, mid) == calc_(len - i - 1, mid))
                lo = mid;
            else
                hi = mid - 1;
        }

        cntDec[i - lo + 1] ++;
        cntDec[i + 1] -= 2;
        cntDec[i + lo + 1] ++;

        sol += lo;
        increase[i] += lo;

        ll jump = lo + 1;
        lo = 0, hi = max(0, min(i + 1, len - i) - jump);
        while(lo < hi){
            ll mid = (lo + hi + 1) >> 1;
            /*if(i + jump + mid - 1 >= s.size() || len - i + jump - 1 + mid - 1 >= s.size()){
                assert(s.size() == 0);
            }*/
            if(calc(i + jump, mid) == calc_(len - i + jump - 1, mid))
                lo = mid;
            else
                hi = mid - 1;
        }

        letInc[i + jump - 1][s[i - jump + 1] - 'a'] += lo + 1;
        letInc[i - jump + 1][s[i + jump - 1] - 'a'] += lo + 1;

        if(i == len - 1) continue;
        //neparni
        lo = 0, hi = max(0, min(i + 1, len - i - 1));
        while(lo < hi){
            ll mid = (lo + hi + 1) >> 1;
            /*if(i + 1 + mid - 1 >= s.size() || len - i - 1 - mid + 1 >= s.size()){
                assert(s.size() == 0);
            }*/
            if(calc(i + 1, mid) == calc_(len - i - 1, mid))
                lo = mid;
            else
                hi = mid - 1;
        }

        sol += lo;

        if(lo){
            cntDec[i - lo + 1] ++;
            cntDec[i + 1] --;
            cntDec[i + 2] --;
            cntDec[i + lo + 2] ++;
        }

        jump = lo + 1;
        lo = 0, hi = max(0, min(i + 1, len - i - 1) - jump);
        while(lo < hi){

            ll mid = (lo + hi + 1) >> 1;
            /*if(i + jump + 1 + mid - 1 >= s.size() || len - i + jump - 1 + mid - 1 >= s.size()){
                assert(s.size() == 0);
            }*/
            if(calc(i + jump + 1, mid) == calc_(len - i + jump - 1, mid))
                lo = mid;
            else
                hi = mid - 1;
        }

        letInc[i + jump][s[i - jump + 1] - 'a'] += lo + 1;
        letInc[i - jump + 1][s[i + jump] - 'a'] += lo + 1;
    }

    ll cnt = 0, curr = 0;

    REP(i, len){
        cnt += cntDec[i];
        curr += cnt;
        decrease[i] = curr;
    }

    ll best = 0;
    REP(i, len)
        REP(j, 26){
            best = max(best, increase[i] + letInc[i][j] - decrease[i]);

        }

    cout << sol + best;
}

Compilation message

palinilap.cpp: In function 'int main()':
palinilap.cpp:82:55: error: no matching function for call to 'max(int, ll)'
         lo = 0, hi = max(0, min(i + 1, len - i) - jump);
                                                       ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from palinilap.cpp:1:
/usr/include/c++/7/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++/7/bits/stl_algobase.h:219:5: note:   template argument deduction/substitution failed:
palinilap.cpp:82:55: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll {aka long long int}')
         lo = 0, hi = max(0, min(i + 1, len - i) - jump);
                                                       ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from palinilap.cpp:1:
/usr/include/c++/7/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++/7/bits/stl_algobase.h:265:5: note:   template argument deduction/substitution failed:
palinilap.cpp:82:55: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll {aka long long int}')
         lo = 0, hi = max(0, min(i + 1, len - i) - jump);
                                                       ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from palinilap.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3462:5: note: candidate: template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)
     max(initializer_list<_Tp> __l)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3462:5: note:   template argument deduction/substitution failed:
palinilap.cpp:82:55: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
         lo = 0, hi = max(0, min(i + 1, len - i) - jump);
                                                       ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from palinilap.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3468: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++/7/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
palinilap.cpp:82:55: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
         lo = 0, hi = max(0, min(i + 1, len - i) - jump);
                                                       ^
palinilap.cpp:121:59: error: no matching function for call to 'max(int, ll)'
         lo = 0, hi = max(0, min(i + 1, len - i - 1) - jump);
                                                           ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from palinilap.cpp:1:
/usr/include/c++/7/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++/7/bits/stl_algobase.h:219:5: note:   template argument deduction/substitution failed:
palinilap.cpp:121:59: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll {aka long long int}')
         lo = 0, hi = max(0, min(i + 1, len - i - 1) - jump);
                                                           ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from palinilap.cpp:1:
/usr/include/c++/7/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++/7/bits/stl_algobase.h:265:5: note:   template argument deduction/substitution failed:
palinilap.cpp:121:59: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll {aka long long int}')
         lo = 0, hi = max(0, min(i + 1, len - i - 1) - jump);
                                                           ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from palinilap.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3462:5: note: candidate: template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)
     max(initializer_list<_Tp> __l)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3462:5: note:   template argument deduction/substitution failed:
palinilap.cpp:121:59: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
         lo = 0, hi = max(0, min(i + 1, len - i - 1) - jump);
                                                           ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from palinilap.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3468: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++/7/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
palinilap.cpp:121:59: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
         lo = 0, hi = max(0, min(i + 1, len - i - 1) - jump);
                                                           ^