oj.uz

Submission #138343

# Submission time Handle Problem Language Result Execution time Memory
138343 2019-07-29T19:05:05 Z Atalasion Palinilap (COI16_palinilap) C++14
100 / 100
 503 ms 33784 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 2040 KB Output is correct
2 Correct 103 ms 2040 KB Output is correct
3 Correct 103 ms 2140 KB Output is correct
4 Correct 110 ms 2044 KB Output is correct
5 Correct 103 ms 2044 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 3632 KB Output is correct
2 Correct 124 ms 3524 KB Output is correct
3 Correct 116 ms 3620 KB Output is correct
4 Correct 111 ms 2992 KB Output is correct
5 Correct 113 ms 3332 KB Output is correct
6 Correct 116 ms 3576 KB Output is correct
7 Correct 117 ms 3548 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 33632 KB Output is correct
2 Correct 358 ms 33632 KB Output is correct
3 Correct 390 ms 33528 KB Output is correct
4 Correct 472 ms 33528 KB Output is correct
5 Correct 468 ms 33656 KB Output is correct
6 Correct 469 ms 33656 KB Output is correct
7 Correct 476 ms 33684 KB Output is correct
8 Correct 298 ms 10104 KB Output is correct
9 Correct 485 ms 33592 KB Output is correct
10 Correct 469 ms 33528 KB Output is correct
11 Correct 369 ms 33644 KB Output is correct
12 Correct 496 ms 33528 KB Output is correct
13 Correct 478 ms 33636 KB Output is correct
14 Correct 487 ms 33656 KB Output is correct
15 Correct 479 ms 33580 KB Output is correct
16 Correct 422 ms 33572 KB Output is correct
17 Correct 465 ms 33656 KB Output is correct
18 Correct 474 ms 33784 KB Output is correct
19 Correct 503 ms 33672 KB Output is correct