oj.uz

Submission #957294

# Submission time Handle Problem Language Result Execution time Memory
957294 2024-04-03T12:20:48 Z vjudge1 Palindromes (APIO14_palindrome) C++14
15 / 100
 58 ms 10420 KB 
#include<bits/stdc++.h>

using namespace std;

#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(1, 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 add){
   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]*2-add)*(r[i]-l[i]+2));
   return ans;
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   string s; cin >> s;
   SuffixArray sa(s, 128);
   auto v=manacher(s);
   int ans=0;
   int n=s.size();
   auto lcp=sa.lcp;
   for (int i=1; i<=n; ++i){
      lcp[i]=min(lcp[i], v[0][sa.sa[i]]);
      if (i>1) lcp[i]=min(lcp[i], v[0][sa.sa[i-1]]);
   }
   ans=max(ans, solve(lcp, 0));
   lcp=sa.lcp;
   for (int i=1; i<=n; ++i){
      lcp[i]=min(lcp[i], v[1][sa.sa[i]]+1);
      if (i>1) lcp[i]=min(lcp[i], v[1][sa.sa[i-1]]+1);
   }
   ans=max(ans, solve(lcp, 1));
   for (int i:v[0]) ans=max(ans, i*2);
   for (int i:v[1]) ans=max(ans, i*2+1);
   cout << ans;
   return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2512 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2504 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2508 KB Output is correct
10 Incorrect 1 ms 2516 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2516 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 2 ms 2916 KB Output is correct
7 Correct 2 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Incorrect 2 ms 2652 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 5180 KB Output is correct
2 Correct 17 ms 5180 KB Output is correct
3 Incorrect 19 ms 5176 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 10420 KB Output isn't correct
2 Halted 0 ms 0 KB -