oj.uz

Submission #957307

# Submission time Handle Problem Language Result Execution time Memory
957307 2024-04-03T13:12:59 Z vjudge1 Palindromes (APIO14_palindrome) C++14
100 / 100
 346 ms 69924 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

struct SuffixArray {
	vi sa, lcp;
	SuffixArray(string& s, int lim=256) { // or basic_string<int>
		int n = sz(s) + 1, k = 0, a, b;
		vi x(all(s)+1), y(n), ws(max(n, lim)), rank(n);
		sa = lcp = y, iota(all(sa), 0);
		for (int j = 0, p = 0; p < n; j = max(1ll, j * 2), lim = p) {
			p = j, iota(all(y), n - j);
			rep(i,0,n) if (sa[i] >= j) y[p++] = sa[i] - j;
			fill(all(ws), 0);
			rep(i,0,n) ws[x[i]]++;
			rep(i,1,lim) ws[i] += ws[i - 1];
			for (int i = n; i--;) sa[--ws[x[y[i]]]] = y[i];
			swap(x, y), p = 1, x[sa[0]] = 0;
			rep(i,1,n) a = sa[i - 1], b = sa[i], x[b] =
				(y[a] == y[b] && y[a + j] == y[b + j]) ? p - 1 : p++;
		}
		rep(i,1,n) rank[sa[i]] = i;
		for (int i = 0, j; i < n - 1; lcp[rank[i++]] = k)
			for (k && k--, j = sa[rank[i] - 1];
					s[i + k] == s[j + k]; k++);
	}
};

array<vi, 2> manacher(const string& s) {
	int n = sz(s);
	array<vi,2> p = {vi(n+1), vi(n)};
	rep(z,0,2) for (int i=0,l=0,r=0; i < n; i++) {
		int t = r-i+!z;
		if (i<r) p[z][i] = min(t, p[z][l+t]);
		int L = i-p[z][i], R = i+p[z][i]-!z;
		while (L>=1 && R+1<n && s[L-1] == s[R+1])
			p[z][i]++, L--, R++;
		if (R>r) l=L, r=R;
	}
	return p;
}

const int N=3e5+10;
int l[N], r[N];

int solve(vector<int> a){
   int n=a.size()-1;
   stack<int> st;
   for (int i=1; i<=n; ++i){
      while (st.size() && a[st.top()]>=a[i]) st.pop();
      l[i]=st.empty()?1:st.top()+1;
      st.push(i);
   }
   while (st.size()) st.pop();
   for (int i=n; i>=1; --i){
      while (st.size() && a[st.top()]>=a[i]) st.pop();
      r[i]=st.empty()?n:st.top()-1;
      st.push(i);
   }
   int ans=0;
   for (int i=1; i<=n; ++i) ans=max(ans, a[i]*(r[i]-l[i]+2));
   return ans;
}

vector<int> vv[N];
int len[N];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   string s; cin >> s;
   SuffixArray sa(s, 128);
   auto v=manacher(s);
   vector<pair<int, int>> pal;
   int n=s.size();
   for (int i=0; i<n; ++i) pal.emplace_back(i-v[1][i], i+v[1][i]);
   for (int i=0; i<n; ++i) if (v[0][i]) pal.emplace_back(i-v[0][i], i+v[0][i]-1);
   for (auto &i:pal) vv[i.first].push_back(i.second);
   priority_queue<pair<int, int>> pq;
   int ans=0;
   for (int i=0; i<n; ++i){
      for (int j:vv[i]) pq.emplace(i+j, (i+j)/2);
      while (pq.size() && pq.top().second<i) pq.pop();
      len[i]=pq.size()?pq.top().first+1-i*2:0;
      ans=max(ans, len[i]);
   }
   auto lcp=sa.lcp;
   for (int i=1; i<=n; ++i){
      lcp[i]=min(lcp[i], len[sa.sa[i]]);
      if (i>1) lcp[i]=min(lcp[i], len[sa.sa[i-1]]);
   }
   ans=max(ans, solve(lcp));
   cout << ans;
   return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10584 KB Output is correct
7 Correct 3 ms 10588 KB Output is correct
8 Correct 2 ms 10724 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 3 ms 10588 KB Output is correct
12 Correct 2 ms 10588 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct
14 Correct 2 ms 10588 KB Output is correct
15 Correct 3 ms 10584 KB Output is correct
16 Correct 2 ms 10588 KB Output is correct
17 Correct 2 ms 10588 KB Output is correct
18 Correct 2 ms 10588 KB Output is correct
19 Correct 2 ms 10588 KB Output is correct
20 Correct 2 ms 10584 KB Output is correct
21 Correct 3 ms 10588 KB Output is correct
22 Correct 2 ms 10584 KB Output is correct
23 Correct 2 ms 10840 KB Output is correct
24 Correct 2 ms 10676 KB Output is correct
25 Correct 2 ms 10588 KB Output is correct
26 Correct 2 ms 10588 KB Output is correct
27 Correct 2 ms 10588 KB Output is correct
28 Correct 2 ms 10588 KB Output is correct
29 Correct 2 ms 10588 KB Output is correct
30 Correct 2 ms 10588 KB Output is correct
31 Correct 2 ms 10588 KB Output is correct
32 Correct 2 ms 10584 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 2 ms 10788 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 3 ms 10588 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 2 ms 10840 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 2 ms 10844 KB Output is correct
12 Correct 2 ms 10844 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11868 KB Output is correct
2 Correct 4 ms 11612 KB Output is correct
3 Correct 5 ms 12376 KB Output is correct
4 Correct 5 ms 12372 KB Output is correct
5 Correct 5 ms 11608 KB Output is correct
6 Correct 5 ms 11988 KB Output is correct
7 Correct 4 ms 11608 KB Output is correct
8 Correct 4 ms 11720 KB Output is correct
9 Correct 4 ms 11864 KB Output is correct
10 Correct 4 ms 11868 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 23196 KB Output is correct
2 Correct 30 ms 23080 KB Output is correct
3 Correct 45 ms 29064 KB Output is correct
4 Correct 36 ms 30228 KB Output is correct
5 Correct 90 ms 22672 KB Output is correct
6 Correct 68 ms 22888 KB Output is correct
7 Correct 52 ms 25612 KB Output is correct
8 Correct 22 ms 23960 KB Output is correct
9 Correct 35 ms 24976 KB Output is correct
10 Correct 92 ms 28628 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 47524 KB Output is correct
2 Correct 80 ms 47860 KB Output is correct
3 Correct 109 ms 69924 KB Output is correct
4 Correct 101 ms 69084 KB Output is correct
5 Correct 316 ms 46504 KB Output is correct
6 Correct 165 ms 52136 KB Output is correct
7 Correct 151 ms 53416 KB Output is correct
8 Correct 67 ms 49168 KB Output is correct
9 Correct 65 ms 50852 KB Output is correct
10 Correct 346 ms 53332 KB Output is correct
11 Correct 83 ms 49364 KB Output is correct
12 Correct 109 ms 52648 KB Output is correct