We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
public class E2 {
InputStream is;
PrintWriter out;
String INPUT = "";
void solve()
{
int n = ni();
char[] s = ns(n);
char[] s2 = new char[2*n];
for(int i = 0;i < n;i++){
s2[i] = s2[i+n] = s[i];
}
int[] pal = palindrome(s2);
// tr(pal, pal.length, n);
long[] es = new long[16*n];
int p = 0;
for(int i = 0;i < 4*n;i+=2){
pal[i] = Math.min(pal[i], n-((n&1)^1));
es[p++] = (long)(i/2)<<32|i;
es[p++] = (long)(i/2+pal[i]/2)<<32|i;
es[p++] = (long)(i/2+n-pal[i]/2-1)<<32|i;
es[p++] = (long)(i/2+n)<<32|i;
}
for(int i = 1;i < 4*n;i+=2){
pal[i] = Math.min(pal[i], n-((n&1)));
es[p++] = (long)(i/2)<<32|i;
es[p++] = (long)(i/2+pal[i]/2)<<32|i;
es[p++] = (long)(i/2+n-pal[i]/2)<<32|i;
es[p++] = (long)(i/2+n)<<32|i;
}
Arrays.sort(es, 0, p);
MaxHeap inc = new MaxHeap(4*n+1);
MaxHeap dec = new MaxHeap(4*n+1);
MaxHeap flat = new MaxHeap(4*n+1);
int[] st = new int[4*n];
int q = 0;
for(int i = 0;i < 2*n-1;i++){
while(q < p && es[q]>>>32 <= i){
int ind = (int)es[q];
if(st[ind] == 0){
inc.add(ind, (pal[ind]&1)-2*i);
}else if(st[ind] == 1){
inc.remove(ind);
flat.add(ind, pal[ind]);
}else if(st[ind] == 2){
flat.remove(ind);
dec.add(ind, pal[ind]+2*i);
}else if(st[ind] == 3){
dec.remove(ind);
}
st[ind]++;
q++;
}
if(i >= n-1){
// tr("i", i);
int max = 0;
if(inc.size() > 0)max = Math.max(inc.max()+2*i, max);
// tr(max);
if(dec.size() > 0)max = Math.max(dec.max()-2*i, max);
// tr(max);
max = Math.max(flat.max(), max);
// tr(max);
out.println(max);
}
}
}
public static class MaxHeap {
public int[] a;
public int[] map;
public int[] imap;
public int n;
public int pos;
public static int INF = Integer.MIN_VALUE;
public MaxHeap(int m)
{
n = m+2;
a = new int[n];
map = new int[n];
imap = new int[n];
Arrays.fill(a, INF);
Arrays.fill(map, -1);
Arrays.fill(imap, -1);
pos = 1;
}
public int add(int ind, int x)
{
int ret = imap[ind];
if(imap[ind] < 0){
a[pos] = x; map[pos] = ind; imap[ind] = pos;
pos++;
up(pos-1);
}
return ret != -1 ? a[ret] : x;
}
public int update(int ind, int x)
{
int ret = imap[ind];
if(imap[ind] < 0){
a[pos] = x; map[pos] = ind; imap[ind] = pos;
pos++;
up(pos-1);
}else{
int o = a[ret];
a[ret] = x;
up(ret);
down(ret);
Circular Palindromes
You are viewing a single comment's thread. Return to all comments →
import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.InputMismatchException;
public class E2 { InputStream is; PrintWriter out; String INPUT = "";
// tr(pal, pal.length, n); long[] es = new long[16*n]; int p = 0; for(int i = 0;i < 4*n;i+=2){ pal[i] = Math.min(pal[i], n-((n&1)^1)); es[p++] = (long)(i/2)<<32|i; es[p++] = (long)(i/2+pal[i]/2)<<32|i; es[p++] = (long)(i/2+n-pal[i]/2-1)<<32|i; es[p++] = (long)(i/2+n)<<32|i; } for(int i = 1;i < 4*n;i+=2){ pal[i] = Math.min(pal[i], n-((n&1))); es[p++] = (long)(i/2)<<32|i; es[p++] = (long)(i/2+pal[i]/2)<<32|i; es[p++] = (long)(i/2+n-pal[i]/2)<<32|i; es[p++] = (long)(i/2+n)<<32|i; }
// tr("i", i); int max = 0; if(inc.size() > 0)max = Math.max(inc.max()+2*i, max); // tr(max); if(dec.size() > 0)max = Math.max(dec.max()-2*i, max); // tr(max); max = Math.max(flat.max(), max); // tr(max); out.println(max); } } } public static class MaxHeap { public int[] a; public int[] map; public int[] imap; public int n; public int pos; public static int INF = Integer.MIN_VALUE;
// if(a[ret] < o){ // up(ret); // }else{ // down(ret); // } } return x; }
}