Cod sursa(job #2738258)

Utilizator stefantagaTaga Stefan stefantaga Data 5 aprilie 2021 17:03:00
Problema Numarare Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("numarare.in");
ofstream g("numarare.out");
int n,i,x,v[200005],st1,dr1,st,dr,val[200005],oglin,sum;
int main()
{
    f>>n;
    for (i=1;i<=n;i++)
    {
        f>>x;
        v[2*i-1]=x;
        v[2*i]=0;
    }
    st=0;
    dr=-1;
    for (i=2;i<=2*n;i+=2)
    {
            if (dr<i)
        {
            st1=i-3;
            dr1=i+3;
            val[i]=1;
            while (st1>0&&dr1<=n&&v[st1]+v[dr1]==v[i-1]+v[i+1])
            {
                st1-=2;
                dr1+=2;
                val[i]++;
            }
            st=i-2*val[i]+1;
            dr=i+2*val[i]-1;
        }
            else
            {
                oglin=st+dr-i;
                val[i]=val[oglin];
                if (i+2*val[oglin]-1>=dr)
                {
                    st1=i-2*val[i]-1;
                    dr1=i+2*val[i]+1;
                    while (st1>0&&dr1<=n&&v[st1]+v[dr1]==v[i-2*val[i]+1]+v[i+2*val[i]-1])
                    {
                        st1-=2;
                        dr1+=2;
                        val[i]++;
                    }
                }
                if (dr<i+2*val[i]-1)
                {
                    st=i-2*val[i]+1;
                    dr=i+2*val[i]-1;
                }
            }
            sum=sum+val[i];
    }
    g<<sum;
    return 0;
}