oj.uz

Submission #138342

# Submission time Handle Problem Language Result Execution time Memory
138342 2019-07-29T18:59:46 Z mehrdad_sohrabi Palinilap (COI16_palinilap) C++14
100 / 100
 483 ms 33812 KB 
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < int, int >
#define F first
#define S second
#define int long long int
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize ("Ofast")
using namespace std;
/// khodaya komak kon
/// ya navid navid
/// ye tec khaphan ke yadam bemone : age jayi didi soale masir hamiltoni mikhad rasasho bokon yal oilery;https://mobomovie1.top/series/%D8%AF%D8%A7%D9%86%D9%84%D9%88%D8%AF-%D8%B3%D8%B1%DB%8C%D8%A7%D9%84-%D9%81%D8%B1%DB%8C%D9%86%D8%AC-fringe-2008-2013-%D8%A8%D8%A7-%D8%B2%D9%8A%D8%B1%D9%86%D9%88%D9%8A%D8%B3-%D9%81%D8%A7%D8%B1/
/// age ye ja mikhasti to dp az ozv i k ta entekhab koni bejash ye log bezan (nominal) hamoon 2**k va o 1 ent kon

const int N=1e5+100;
ll ph1[N];
ll ph2[N];
ll mod=1e9+7;
ll p[N];
ll a[N];
ll n;
ll inv[N];
char c[N];
ll b[N];
ll power(ll n,ll k){
    if (k==0){
        return 1;
    }
    if (k%2==1){
        ll x=power(n,k/2);
        return x*x%mod*n%mod;
    }
    ll x=power(n,k/2);
    return x*x%mod;
}
ll h1(ll l,ll r){
    ll z=ph1[r-1];
    z-=ph1[l-1];
    z+=mod;
    z%=mod;
    z*=inv[l-1];
    z%=mod;
    return z;
}
ll h2(ll l,ll r){
    ll z=ph2[l];
    z-=ph2[r];
    z+=mod;
    z%=mod;
    z*=inv[n-r+1];
    z%=mod;
    return z;
}
ll bs(ll s,ll f){
    ll l=0,r=min(s,n-f)+1;
    while(r-l>1){
        ll mid=(r+l)/2;
        ll z=h1(s-mid+1,s+1);
        ll w=h2(f+1,f+mid+1);

        if (z==w){
            l=mid;
        }
        else{
            r=mid;
        }
    }
    return l;
}
ll ans[N][30];
ll g[N];
ll baze1[N],baze2[N];
ll baze3[N],baze4[N],baze5[N],baze6[N];
int32_t main(){

    p[0]=1;
    inv[0]=1;
    for (int i=1;i<N;i++){
        p[i]=p[i-1]*311%mod;
        inv[i]=power(p[i],mod-2);
    }
    string we;
    cin >> we;
    n=we.size();
    for (int i=0;i<n;i++){
        c[i]=we[i];
        a[i]=c[i]-'a'+1;
    }
    for (int i=1;i<=n;i++){
        ph1[i]=ph1[i-1]%mod+a[i-1]*p[i-1]%mod;
        ph1[i]%=mod;
    }
    for (int i=n;i>0;i--){
        ph2[i]=ph2[i+1]+a[i-1]*p[n-i]%mod;
        ph2[i]%=mod;
    }
    ll u=1;
    for (int i=1;i<n;i++){
        ll d=bs(i,i);
        baze1[i]+=d;
        baze5[i-d]++;
        baze3[i]++;
    //cout << d << endl;
       // baze1.pb({i-d,i});
        baze2[i]+=d;
        baze6[i]++;
        baze4[i+d]+=1;
       // baze2.pb({i,i+d});
       u+=d;
        if (i-d>0 && i+d<=n-1){
            ll w=bs(i-d-1,i+d+1);
            ans[i-d-1][a[i+d]]+=w+1;
            ans[i+d][a[i-d-1]]+=w+1;
          //  cout << i << " " << w << " " << a[i-d-1] << " " << a[i+d] << " " << d << endl;
        }

        d=bs(i,i+1);
        u+=d+1;
        baze1[i]+=d;
        baze5[i-d]++;
        baze3[i]+=1;
        baze2[i+1]+=d;
        baze4[i+d+1]++;
        baze6[i+1]++;
        //baze1.pb({i-d,i});
      //  baze2.pb({i+1,i+d+1});
     //   cout << i << " " << d << endl;
        if (i-d>0 && i+1+d<=n-1){
            ll w=bs(i-d-1,i+1+d+1);
            ans[i-d-1][a[i+d+1]]+=w+1;
            ans[i+d+1][a[i-d-1]]+=w+1;
          //  cout << i << " : " << w << " " << a[i-d-1] << " " << a[i+d+1] << endl;
        }
    }

    ll cnt1=0,cnt2=0;
    ll b1=0,b2=0;
    ll sum=0;
    for (int i=0;i<n;i++){
        b1-=baze3[i];
       // b2-=baze4[i];
        sum-=baze1[i];
        b1+=baze5[i];
        sum+=b1;
        sum-=b2;
        b2+=baze6[i];
        sum+=baze2[i];
        b2-=baze4[i];
        g[i]=sum;
        //cout << i << " " << sum << " " << ans[i][1] << endl;
    }
    ll ma=0;
    for (int i=0;i<n;i++){
        for (int j=0;j<29;j++){
            ma=max(ma,ans[i][j]-g[i]);
           // cout << i << " df " << j << " " << ans[i][j] << " " << g[i] << endl;
        }

    }
    cout << u+ma << endl;

}

Compilation message

palinilap.cpp: In function 'int32_t main()':
palinilap.cpp:138:8: warning: unused variable 'cnt1' [-Wunused-variable]
     ll cnt1=0,cnt2=0;
        ^~~~
palinilap.cpp:138:15: warning: unused variable 'cnt2' [-Wunused-variable]
     ll cnt1=0,cnt2=0;
               ^~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 1912 KB Output is correct
2 Correct 104 ms 2040 KB Output is correct
3 Correct 103 ms 2040 KB Output is correct
4 Correct 103 ms 1912 KB Output is correct
5 Correct 103 ms 2040 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 3704 KB Output is correct
2 Correct 113 ms 3576 KB Output is correct
3 Correct 116 ms 3496 KB Output is correct
4 Correct 110 ms 2936 KB Output is correct
5 Correct 113 ms 3320 KB Output is correct
6 Correct 117 ms 3576 KB Output is correct
7 Correct 122 ms 3492 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 33664 KB Output is correct
2 Correct 362 ms 33552 KB Output is correct
3 Correct 376 ms 33720 KB Output is correct
4 Correct 466 ms 33784 KB Output is correct
5 Correct 466 ms 33812 KB Output is correct
6 Correct 468 ms 33656 KB Output is correct
7 Correct 483 ms 33704 KB Output is correct
8 Correct 308 ms 10280 KB Output is correct
9 Correct 469 ms 33692 KB Output is correct
10 Correct 467 ms 33656 KB Output is correct
11 Correct 363 ms 33656 KB Output is correct
12 Correct 481 ms 33592 KB Output is correct
13 Correct 470 ms 33664 KB Output is correct
14 Correct 467 ms 33780 KB Output is correct
15 Correct 468 ms 33620 KB Output is correct
16 Correct 424 ms 33732 KB Output is correct
17 Correct 466 ms 33784 KB Output is correct
18 Correct 474 ms 33664 KB Output is correct
19 Correct 467 ms 33656 KB Output is correct