oj.uz

Submission #602036

# Submission time Handle Problem Language Result Execution time Memory
602036 2022-07-22T14:00:37 Z ace5 Palindromes (APIO14_palindrome) C++17
100 / 100
 473 ms 118312 KB 
#include <bits/stdc++.h>
#include <random>
#include <ext/rope>
#include <complex>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

const int alf = 26;
const int maxn = 300005;

struct sf
{
    sf(){len = 0;link = 0;l = 0;c = 0;};
    int go[alf];
    int len,link;
    int l;
    int c;
};


vector<sf> sa(2*maxn);

void init()
{
    sa[0].link = -1;
    sa[0].len = 0;
    sa[0].c = 0;
    sa[0].l = -1;
    for(int i = 0;i < sa.size();++i)
    {
        for(int j = 0;j < alf;++j)
            sa[i].go[j] = -1;
    }
    return ;

}

int last = 0,sz = 1;


void add(char c)
{
    int x = c-'a';
    int cur = sz++;
    sa[cur].len = sa[last].len+1;
    sa[cur].l = 0;
    sa[cur].c = 1;
    int p = last;
    while(p != -1 && sa[p].go[x] == -1)
    {
        sa[p].go[x] = cur;
        p = sa[p].link;
    }
   // cout << p << ' ';
    if(p == -1)
    {
        sa[cur].link = 0;
    }
    else
    {
        int q = sa[p].go[x];
        if(sa[p].len == sa[q].len-1)
        {
            sa[cur].link = q;
        }
        else
        {
            int clone = sz++;
            sa[clone].len = sa[p].len + 1;
            sa[clone].link = sa[q].link;
            for(int i = 0;i < alf;++i)
                sa[clone].go[i] = sa[q].go[i];
            sa[clone].c = 0;
            sa[clone].l = sa[q].l + sa[q].len - sa[p].len - 1;
            sa[q].link = sa[cur].link = clone;
            int cp = p;
            while(sa[cp].go[x] == q)
            {
                sa[cp].go[x] = clone;
                cp = sa[cp].link;
            }
        }
    }
    last = cur;
    return ;
}
vector<int64_t> phash(maxn),shash(maxn);
vector<int64_t> st(maxn);
const int64_t mod = int64_t(1e9)+7,p = 101;

bool qp(int64_t l,int64_t r)
{
   // cout << shash[l] << ' ' << ((shash[r+1]*(st[r-l+1]))%mod) << "\n";
    if((phash[r+1]-((phash[l]*(st[r-l+1]))%mod)+mod)%mod == (shash[l]-((shash[r+1]*(st[r-l+1]))%mod)+mod)%mod)
        return true;
    else
        return false;
}

struct ev
{
    ev(){t =0;c = 0;oc = 0;l = 0;};
    ev(int  _t,bool _c,int _oc,int _l){t =_t;c = _c;oc = _oc;l = _l;};
    int t;
    bool c;
    int oc;
    int l;
    bool operator <(const ev& other)const
    {
        if(t != other.t)
            return t < other.t;
        if(c == other.c)
            return oc < other.oc;
        else
        {
            if(c == 0)
            {
                if(oc == 0)
                    return 1;
                else
                    return 0;
            }
            else
            {
                if(other.oc == 0)
                    return 0;
                else
                    return 1;
            }
        }
    }
};




int main()
{
    st[0] = 1;
    for(int i =1;i < maxn;++i)
    {
        st[i] = (p*st[i-1])%mod;
    }
    string s;
    cin >> s;
    int n = s.size();
    init();
    for(int i = 0;i < s.size();++i)
    {
       // cout << 1;
        add(s[i]);
    }
    vector<pair<int,int>> tr;
    for(int i = 1;i < sz;++i)
    {
        tr.push_back({sa[i].len,i});
    }
    sort(tr.rbegin(),tr.rend());
    for(int i = 0;i < sz-1;++i)
    {
        sa[sa[tr[i].second].link].c += sa[tr[i].second].c;
    }
   // cout << 1;
    int64_t thash = 0;
    phash[0] = thash;
    for(int i = 0;i < s.size();++i)
    {
        thash *= p;
        thash += s[i];
        thash = thash%mod;
        phash[i+1] = thash;
    }
    thash = 0;
    shash[n] = thash;
    for(int i = int(s.size())-1;i >= 0;--i)
    {
        thash *= p;
        thash += s[i];
        thash = thash%mod;
        shash[i] = thash;
    }
    vector<ev> lg;

    for(int i = 1;i < sz;++i)
    {
       // cout << sa[i].link << ' ' << sa[i].l << ' ' << sa[i].len << ' ' << sa[i].c << "\n";
        lg.push_back(ev(sa[i].l + sa[i].len - 1,1,sa[i].c,sa[i].l));
    }
    for(int i = 0;i < n;++i)
    {
        int l = max(0,i-(n-i)+1),r = i;
        while(l < r)
        {
            int m = (l+r)/2;
            if(qp(m,2*i-m))
                r = m;
            else
                l = m+1;
        }
        //cout << l << ' ' << i << "\n";
        lg.push_back(ev(i,0,0,2*i));
        lg.push_back(ev(2*i-l,0,1,2*i));
    }
    for(int i = 1;i < n;++i)
    {
        int l = max(1,i-(n-i)+1),r = i+1;
        while(l < r)
        {
            int m = (l+r)/2;
            if(qp(m-1,2*i-m))
                r = m;
            else
                l = m+1;
        }
        //cout << l << ' ' << i << "\n";
        if(l <= i)
        {
            lg.push_back(ev(i,0,0,2*i-1));
            lg.push_back(ev(2*i-l,0,1,2*i-1));

        }
    }
    sort(lg.begin(),lg.end());
    int64_t ans = 0;
    set<int> ss;
    for(int i = 0;i < lg.size();++i)
    {
        ev x = lg[i];
        if(x.c == 0)
        {
            if(x.oc == 0)
            {
                ss.insert(x.l);
            }
            else
                ss.erase(x.l);
        }
        else
        {
            auto it = ss.lower_bound((x.l+x.t));
            int64_t xx = (*it);
         //   cout << xx << ' ' << x.l << ' ' << x.t << "\n";
            if(xx%2 == 0)
                ans = max(ans,((x.t-(xx/2))*2+1)*(x.oc));
            else
                ans = max(ans,((x.t-(xx/2))*2)*(x.oc));
        }
    }
    cout << ans;
    return 0;
}

Compilation message

palindrome.cpp: In function 'void init()':
palindrome.cpp:33:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<sf>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int i = 0;i < sa.size();++i)
      |                   ~~^~~~~~~~~~~
palindrome.cpp: In function 'int main()':
palindrome.cpp:152:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |     for(int i = 0;i < s.size();++i)
      |                   ~~^~~~~~~~~~
palindrome.cpp:170:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |     for(int i = 0;i < s.size();++i)
      |                   ~~^~~~~~~~~~
palindrome.cpp:230:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ev>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  230 |     for(int i = 0;i < lg.size();++i)
      |                   ~~^~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 77788 KB Output is correct
2 Correct 42 ms 77772 KB Output is correct
3 Correct 40 ms 77788 KB Output is correct
4 Correct 39 ms 77716 KB Output is correct
5 Correct 43 ms 77708 KB Output is correct
6 Correct 41 ms 77700 KB Output is correct
7 Correct 42 ms 77780 KB Output is correct
8 Correct 48 ms 77664 KB Output is correct
9 Correct 38 ms 77780 KB Output is correct
10 Correct 46 ms 77756 KB Output is correct
11 Correct 42 ms 77680 KB Output is correct
12 Correct 41 ms 77768 KB Output is correct
13 Correct 40 ms 77780 KB Output is correct
14 Correct 38 ms 77788 KB Output is correct
15 Correct 49 ms 77780 KB Output is correct
16 Correct 41 ms 77752 KB Output is correct
17 Correct 38 ms 77688 KB Output is correct
18 Correct 43 ms 77784 KB Output is correct
19 Correct 45 ms 77776 KB Output is correct
20 Correct 42 ms 77732 KB Output is correct
21 Correct 45 ms 77792 KB Output is correct
22 Correct 46 ms 77792 KB Output is correct
23 Correct 41 ms 77780 KB Output is correct
24 Correct 44 ms 77732 KB Output is correct
25 Correct 43 ms 77688 KB Output is correct
26 Correct 48 ms 77772 KB Output is correct
27 Correct 46 ms 77708 KB Output is correct
28 Correct 56 ms 77780 KB Output is correct
29 Correct 48 ms 77684 KB Output is correct
30 Correct 42 ms 77788 KB Output is correct
31 Correct 47 ms 77900 KB Output is correct
32 Correct 42 ms 77724 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 77908 KB Output is correct
2 Correct 38 ms 78048 KB Output is correct
3 Correct 46 ms 77936 KB Output is correct
4 Correct 40 ms 77956 KB Output is correct
5 Correct 49 ms 77896 KB Output is correct
6 Correct 45 ms 77900 KB Output is correct
7 Correct 46 ms 77900 KB Output is correct
8 Correct 41 ms 77836 KB Output is correct
9 Correct 39 ms 77900 KB Output is correct
10 Correct 38 ms 77916 KB Output is correct
11 Correct 41 ms 77900 KB Output is correct
12 Correct 39 ms 77900 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 78504 KB Output is correct
2 Correct 48 ms 79060 KB Output is correct
3 Correct 65 ms 79072 KB Output is correct
4 Correct 54 ms 79152 KB Output is correct
5 Correct 53 ms 78448 KB Output is correct
6 Correct 52 ms 79096 KB Output is correct
7 Correct 54 ms 79116 KB Output is correct
8 Correct 54 ms 79048 KB Output is correct
9 Correct 55 ms 78988 KB Output is correct
10 Correct 48 ms 79044 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 87108 KB Output is correct
2 Correct 123 ms 87456 KB Output is correct
3 Correct 163 ms 91112 KB Output is correct
4 Correct 190 ms 95632 KB Output is correct
5 Correct 114 ms 87032 KB Output is correct
6 Correct 134 ms 87416 KB Output is correct
7 Correct 179 ms 87864 KB Output is correct
8 Correct 127 ms 87352 KB Output is correct
9 Correct 140 ms 87452 KB Output is correct
10 Correct 132 ms 87516 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 101580 KB Output is correct
2 Correct 375 ms 115724 KB Output is correct
3 Correct 471 ms 118312 KB Output is correct
4 Correct 473 ms 115152 KB Output is correct
5 Correct 253 ms 97200 KB Output is correct
6 Correct 375 ms 115324 KB Output is correct
7 Correct 470 ms 115872 KB Output is correct
8 Correct 302 ms 97912 KB Output is correct
9 Correct 307 ms 97908 KB Output is correct
10 Correct 367 ms 114732 KB Output is correct
11 Correct 298 ms 97248 KB Output is correct
12 Correct 338 ms 114420 KB Output is correct