oj.uz

Submission #625401

# Submission time Handle Problem Language Result Execution time Memory
625401 2022-08-10T11:09:39 Z NintsiChkhaidze Palinilap (COI16_palinilap) C++14
100 / 100
 268 ms 40412 KB 
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define s second
#define f first
using namespace std;

const int N = 100005;
int mod = 1000000007,PR = 31,n,h[N],p[N],add[N][30],dlt[N],Rp[N],Rh[N],a1[N],b1[N];
int st[N],Rst[N];
vector <int> en[N],Ren[N];
string s;

bool check(int l1,int r1,int l2,int r2){
    long long val1 = h[r1];
    if (l1) val1 -= h[l1 - 1];
    val1 = (val1%mod+mod)%mod;
    
    long long val2 = Rh[l2];
    if (r2 < n - 1) val2 -= Rh[r2 + 1];
    val2 = (val2%mod+mod)%mod;
    
    return ((val1 * Rp[r2])%mod == (val2 * p[l1])%mod);
}

int get(int L,int R){
    int res=0,l = 0,r = n;
    while (l <= r){
        int mid = (l + r)>>1;
        if (L - mid + 1 >= 0 && R + mid - 1 < n && check(L - mid + 1,L,R,R + mid - 1)) 
            res = mid, l = mid + 1;
        else 
            r = mid - 1;
    }
    return res;
}
signed main (){
    cin>>s;
    n = s.size();
    for (int i = 0; i < n; i++){
        if (i == 0){
            p[i] = 1;
            h[i] = (s[i] - 'a' + 1)%mod;
        }else{
            p[i] = (p[i - 1] * PR)%mod;
            h[i] = (h[i - 1] + (p[i] * (s[i] - 'a' + 1))%mod)%mod;
        }
    }
    
    for (int i = n - 1; i >= 0; i--){
        if (i == n - 1){
            Rp[i] = 1;
            Rh[i] = (s[i] - 'a' + 1)%mod;
        }else{
            Rp[i] = (Rp[i + 1] * PR)%mod;
            Rh[i] = (Rh[i + 1] + (Rp[i] * (s[i] - 'a' + 1))%mod)%mod;
        }
    }
    
    int base_ans = 0;
    for (int i = 0; i < n; i++){
        for (int j = i; j <= min(n - 1,i + 1); j++){
            int len = get(i,j);
            base_ans += len;
            int l = i - len + 1,r = j + len - 1;
            if (i != j){
                if (i - len + 1 <= i){
                    st[i - len + 1]++;
                    en[i].pb(len);
                }
                
                if (j + len - 1 >= j){
                    Rst[j+len-1]++;
                    Ren[j].pb(len);
                }
            }else{
                if (i - len + 1 <= i - 1){
                    st[i - len + 1]++;
                    en[i-1].pb(len - 1);
                }
                
                if (j + len - 1 >= i + 1){
                    Rst[j+len-1]++;
                    Ren[i+1].pb(len - 1);
                }
            }
            
            if (l > 0 && r < n - 1){
                l--,r++;
                int val = get(l - 1,r + 1) + 1;
                add[l][s[r] - 'a' + 1] += val;
                add[r][s[l] - 'a' + 1] += val;
            }
        }
    }
    int sm=0,cnt=0;
    for (int i = 0; i < n; i++){
        cnt += st[i];
        sm += cnt;
        dlt[i] = -sm;
        
        for (int x: en[i]){
            cnt--;
            sm -= x;
        }
    }
    
    sm=0,cnt=0;
    for (int i= n-1;i>=0;i--){
        cnt += Rst[i];
        sm += cnt;
        dlt[i] += -sm;
        for (int x: Ren[i]){
            cnt--;
            sm -= x;
        }
    }
    
    int best_add=0,sum = 0;
    for (int i = 0; i < n; i++){
        for (int j = 1; j <= 26; j++){
            if (j == s[i] - 'a' + 1) continue;
            if (add[i][j] + dlt[i] > best_add)
                best_add = add[i][j] + dlt[i];  
        }
    }
    cout<<best_add + base_ans;
}

Compilation message

palinilap.cpp: In function 'int main()':
palinilap.cpp:119:20: warning: unused variable 'sum' [-Wunused-variable]
  119 |     int best_add=0,sum = 0;
      |                    ^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5080 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6740 KB Output is correct
2 Correct 9 ms 6868 KB Output is correct
3 Correct 12 ms 6668 KB Output is correct
4 Correct 9 ms 5972 KB Output is correct
5 Correct 12 ms 6400 KB Output is correct
6 Correct 12 ms 6672 KB Output is correct
7 Correct 12 ms 6484 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 38772 KB Output is correct
2 Correct 157 ms 40396 KB Output is correct
3 Correct 164 ms 40332 KB Output is correct
4 Correct 250 ms 37652 KB Output is correct
5 Correct 252 ms 37576 KB Output is correct
6 Correct 250 ms 37532 KB Output is correct
7 Correct 260 ms 37564 KB Output is correct
8 Correct 88 ms 16948 KB Output is correct
9 Correct 250 ms 37704 KB Output is correct
10 Correct 256 ms 37572 KB Output is correct
11 Correct 154 ms 40384 KB Output is correct
12 Correct 268 ms 40280 KB Output is correct
13 Correct 250 ms 38768 KB Output is correct
14 Correct 248 ms 37296 KB Output is correct
15 Correct 254 ms 37408 KB Output is correct
16 Correct 164 ms 40412 KB Output is correct
17 Correct 247 ms 34588 KB Output is correct
18 Correct 246 ms 38268 KB Output is correct
19 Correct 243 ms 34584 KB Output is correct