Cod sursa(job #2717593)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 7 martie 2021 17:17:00
Problema Numarare Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <bits/stdc++.h>
#define DIM 200010
#define INF 2000000000
using namespace std;

int a[DIM],v[DIM],s[DIM],p[DIM];
int n,i;
long long sol;

void manacher (int a[], int m){
    int n=1,i;
    v[1] = INF;
    for (i=2;i<=m;i++){
        v[++n] = a[i];
        v[++n] = INF;
    }

    int Left = 0, Right = 0, c = 0;
    for (i=1;i<=n;i++){
        if (i > Right){
            Left = Right = c = i;
            p[i] = 1;
            while (Left > 1 && Right < n && v[Left-1] == v[Right+1]){
                Left--, Right++;
                p[i]++;
            }
        } else {
            int mirror = c - (i - c);
            p[i] = min (p[mirror], Right-i+1);

            int st = i - p[i], dr = i + p[i];
            while (st >= 1 && dr <= n && v[st] == v[dr]){
                st--, dr++;
                p[i]++;
            }

            if (i + p[i] - 1 > Right){
                Left = i - p[i] + 1;
                Right = i + p[i] - 1;
                c = i;
            }
        }
        if (i % 2 == 0)
            sol += p[i]/2;
    }
}

int main (){

    ifstream cin ("numarare.in");
    ofstream cout ("numarare.out");

    cin>>n;
    for (i=1;i<=n;i++)
        cin>>s[i];

    for (i=1;i<=n;i++)
        a[i] = s[i] - s[i-1];

    manacher (a,n);
    cout<<sol;


    return 0;
}