oj.uz

Submission #1008989

# Submission time Handle Problem Language Result Execution time Memory
1008989 2024-06-27T07:33:34 Z BF001 Palinilap (COI16_palinilap) C++17
100 / 100
 39 ms 28112 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define N 100005

int n, md = 1e9 + 7, base = 32, cnt[N], pre[N], f[30][N];
vector<int> pw;
string s, rs;

struct hsh
{
	vector<int> gt;
	hsh(string s){
		int len = (int) s.size();
		while ((int) pw.size() - 1 < len){
			pw.push_back(pw.back() * base % md);
		}
		gt.resize(len + 1, 0);
		for (int i = 1; i <= len; i++){
			gt[i] = (gt[i - 1] * base + s[i - 1] - 'a' + 1) % md;
		}
	}
	int gethsh(int l, int r){
		return (gt[r] - gt[l - 1] * pw[r - l + 1] + md * md) % md;
	}	
};

void ud1(int l, int r){
	if (l > r) return;
	cnt[l] += 1;
	cnt[r + 1] -= 1;
	pre[l] += (1 - l);
	pre[r + 1] -= (1 - l);
}

void ud2(int l, int r){
	if (l > r) return;
	cnt[l] -= 1;
	cnt[r + 1] += 1;
	pre[l] += (r + 1);
	pre[r + 1] -= (r + 1);
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
      
    cin >> s;
    rs = s;
    reverse(rs.begin(), rs.end());

    pw.push_back(1);
    hsh h1 = hsh(s);
    hsh h2 = hsh(rs);

    int n = (int) s.size();
    s = " " + s;
    rs = " " + rs;
    int sum = 0;

    for (int i = 1; i <= n; i++){
    	for (int j = i; j <= min(n, i + 1); j++){
    		int l = 1, r = min(i, n - j + 1), rt = 1;
    		if (s[i] == s[j]){
	    		while (l <= r){
	    			int mid = (l + r) >> 1;
	    			int ps = j, ps2 = j + mid - 1;
	    			if (h1.gethsh(i - mid + 1, i) == h2.gethsh(n - ps2 + 1, n - ps + 1)){
	    				rt = mid;
	    				l = mid + 1;
	    			}
	    			else r = mid - 1;
	    		} 
	    		sum += rt;
	    		l = i - rt + 1, r = j + rt - 1;
	    		if (i != j){
	   				ud1(l, i);
	   				ud2(j, r);
	    		}
	    		else {
	    			ud1(l, i - 1);
	    			ud2(i + 1, r);
	    		}
	    	}
    		int ii = l - 1, jj = r + 1;
    		if (s[i] != s[j]) ii = i, jj = j;
    		if (ii < 1 || jj > n) continue;
    		l = 2, r = min(ii, n - jj + 1), rt = 1;
    		while (l <= r){
    			int mid = (l + r) >> 1;
    			int ps = jj  + 1, ps2 = jj + mid - 1;
    			if (h1.gethsh(ii - mid + 1, ii - 1) == h2.gethsh(n - ps2 + 1, n - ps + 1)){
    				rt = mid;
    				l = mid + 1;
    			}
    			else r = mid - 1;
    		}
    		f[s[ii] - 'a' + 1][jj] += rt;
    		f[s[jj] - 'a' + 1][ii] += rt;
    	}
    }

    int res = sum;

    for (int i = 1; i <= n; i++){
    	pre[i] += pre[i - 1];
    	cnt[i] += cnt[i - 1];
    	for (int j = 1; j <= 26; j++){
    		res = max(res , sum - (i * cnt[i] + pre[i]) + f[j][i]);
    	}
    }

    cout << res;

    return 0;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 20828 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6604 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 22876 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 3 ms 21084 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 3 ms 23384 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 9540 KB Output is correct
2 Correct 19 ms 9780 KB Output is correct
3 Correct 20 ms 9784 KB Output is correct
4 Correct 27 ms 9672 KB Output is correct
5 Correct 28 ms 9580 KB Output is correct
6 Correct 30 ms 9672 KB Output is correct
7 Correct 32 ms 15816 KB Output is correct
8 Correct 20 ms 5580 KB Output is correct
9 Correct 31 ms 11728 KB Output is correct
10 Correct 32 ms 15812 KB Output is correct
11 Correct 24 ms 13772 KB Output is correct
12 Correct 39 ms 13836 KB Output is correct
13 Correct 30 ms 13764 KB Output is correct
14 Correct 30 ms 13776 KB Output is correct
15 Correct 31 ms 15812 KB Output is correct
16 Correct 33 ms 13872 KB Output is correct
17 Correct 32 ms 27980 KB Output is correct
18 Correct 29 ms 9672 KB Output is correct
19 Correct 29 ms 28112 KB Output is correct