Submission #73589

#	Time	Username	Problem	Language	Result	Execution time	Memory
73589		polyfish	Palindromes (APIO14_palindrome)	C++14	24 / 100	1065 ms	2296 KiB

palindrome

//I love armpit fetish

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

#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int MAX_N = 300002;

struct fenwick_tree {
    int n;
    vector<int> bit;

    void init(int _n) {
        n = _n;
        bit.resize(n+1);
    }

    void upd(int id) {
        ++id;
        for (; id<=n; id += id & (-id))
            ++bit[id];
    }

    int get(int id) {
        ++id;
        int res = 0;
        for (; id>0; id -= id & (-id))
            res += bit[id];
        return res;
    }

    int get(int l, int r) {
        return get(r) - get(l-1);
    }
};

int n, gap, L[MAX_N], R[MAX_N], d1[MAX_N], d2[MAX_N];
int pos[MAX_N], sa[MAX_N], lcp[MAX_N], tmp[MAX_N];
string s;
set<pair<int, int> > seg;
fenwick_tree tr;

void enter() {
	char c;
	while (cin >> c) {
		s += '#';
		s += c;
	}
	s += '#';
	n = s.size();
}

void manacher() {
	for (int i=0, l=0, r=-1; i<n; ++i) {
		int k = i>r ? 1 : min(R[l+r-i], r-i);
		while (i+k<n && i-k>=0 && s[i+k]==s[i-k])
			++k;
		d1[i] = k--;
		if (i+k>r) {
			l = i - k;
			r = i + k;
		}
	}
}

bool cmp(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 build_SA() {
	for (int i=0; i<n; ++i) {
		sa[i] = i;
		pos[i] = s[i];
	}
	for (gap = 1; ; gap *= 2) {
		sort(sa, sa+n, cmp);
		for (int i=1; i<n; ++i)
			tmp[i] = tmp[i-1] + cmp(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 build_LCP() {
	for (int i=0, k=0; i<n; ++i) {
		if (pos[i]!=n-1) {
			for (int j=sa[pos[i]+1]; i+k<n && j+k<n && s[i+k]==s[j+k];)
				++k;
			lcp[pos[i]] = k;
			if (k)
				--k;
		}
	}
}

void find_min_boundary() {
	stack<int> st;
	for (int i=0; i<n; ++i) {
		while (st.size() && lcp[st.top()]>=lcp[i])
			st.pop();
		if (st.size())
			L[i] = st.top() + 1;
		else
			L[i] = 0;
		st.push(i);
	}
	while (st.size())
		st.pop();
	for (int i=n-1; i>=0; --i) {
		while (st.size() && lcp[st.top()]>=lcp[i])
			st.pop();
		if (st.size())
			R[i] = st.top() - 1;
		else
			R[i] = n-1;
		st.push(i);
	}
}

int add_seg(int l, int r) {
    while (seg.size()) {
        set<pair<int, int> >::iterator it = seg.lower_bound(make_pair(l, l));
        if (it!=seg.end() && it->second<=r)
            seg.erase(it);
        else
            break;
    }
    seg.insert(make_pair(l, r));
    return tr.get(l, r);
}

int add_pos(int pos) {
    int res = 0;
    tr.upd(pos);
    if (seg.empty())
        return 0;
    set<pair<int, int> >::iterator it = seg.upper_bound(make_pair(pos, n+1));
    while (it!=seg.begin()) {
        --it;
        //cerr << it->first << ' ' << it->second << '\n';
        if (it->second<pos)
            break;
        res = max(res, tr.get(it->first, it->second));
    }
    return res;
}

void solve() {
	for (int i=0; i<n; ++i)
		d2[i] = d1[sa[i]];
	vector<pair<int, int> > b1, b2;
	for (int i=0; i<n; ++i) {
        b1.push_back(make_pair(lcp[i], i));
        b2.push_back(make_pair(d2[i], i));
	}
    sort(b1.begin(), b1.end());
    sort(b2.begin(), b2.end());
    tr.init(n);
    int max_cnt = 0;
    int64_t res = 0;
    if (d1[n/2]==n/2+1)
        res = n/2;
    for (int i=n/2; i>=1; --i) {
        while (b1.size() && b1.back().first>=i) {
            max_cnt = max(max_cnt, add_seg(L[b1.back().second], R[b1.back().second] + 1));
            b1.pop_back();
        }
        while (b2.size() && b2.back().first>=i) {
            max_cnt = max(max_cnt, add_pos(b2.back().second));
            b2.pop_back();
        }
        res = max(res,  int64_t(i - 1) * max_cnt);
        //debug(res);
    }
    cout << res;
}

int main() {
	#ifdef OFFLINE_JUDGE
		freopen(FILE_NAME".inp", "r", stdin);
		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);
	enter();
	manacher();
	build_SA();
	build_LCP();
	find_min_boundary();
	solve();
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 15
• Subtask 3: 24 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27