Mai intai trebuie sa te autentifici.

Cod sursa(job #2975938)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 7 februarie 2023 21:13:36
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("popcnt")

using namespace std;

ifstream fin  ("pscpld.in");
ofstream fout ("pscpld.out");

const int MAX_N = 2'000'002;
int n, lft, rgt;
int pal[MAX_N + 5];
string input, s;

int main (){
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr), fout.tie(nullptr);

    fin>>input;
    s += "(";
    for(char c : input){
        s += "*";
        s += c;
    }
    s += "*)";
    n = (int)s.size()-2;

    lft = rgt = 0;
    for(int i=1; i<=n; i++){

        if(i <= rgt)
            pal[i] = min(rgt - i, pal[lft + (rgt - i)]);

        while(s[i - (pal[i]+1)] == s[i + (pal[i]+1)])
            pal[i]++;

        if(i + pal[i] > rgt){
            lft = i - pal[i];
            rgt = i + pal[i];
        }
    }

    long long sol = 0;
    for(int i=1; i<=n; i++)
        if(s[i] == '*')
            sol += (pal[i]+1) / 2;
        else
            sol += ((pal[i]+1) + 1) / 2;
    fout<<sol;
    return 0;
}