oj.uz

Submission #131902

# Submission time Handle Problem Language Result Execution time Memory
131902 2019-07-18T02:03:06 Z letrongdat Palinilap (COI16_palinilap) C++17
54 / 100
 120 ms 25500 KB 
#include <bits/stdc++.h>
using namespace std;
#define FORN(i, a, b)           for(int i=a; i<=b; ++i)
#define FORD(i, a, b)           for(int i=a; i>=b; --i)
#define REPN(i, a, b)           for(int i=a; i <b; ++i)
#define REPD(i, a, b)           for(int i=(int)a-1; i>=b; --i)
const int maxN = 1e5 + 10;
string w;
int n, m;
long long result;
long long subt[maxN], ad[maxN], su[maxN];
unsigned long long prefix[maxN], suffix[maxN], pw[maxN];
void add(int l, int r, int add) {
    subt[l] += add;
    subt[r+1] -= add;
}
struct Palin {
    int l, r, m, odd, size;
    Palin(){};
    Palin(int l, int r, int odd): l(l), r(r), odd(odd) {};
    void update() {
        size = (odd ? (r-l+1)/2+1 : (r-l+1)/2);
        m = l + r >> 1;
        add(l, m -odd, -l+1);
        ad[l] ++; ad[m -odd +1] --;

        add(m+1, r, r+1);
        su[m+1] ++; su[r+1] --;
    }
} palin[2*maxN];
vector<Palin> pre[maxN], suf[maxN];
unsigned long long get_prefix(int i, int j) {
    return prefix[j] - prefix[i-1] * pw[j-i+1];
}
unsigned long long get_suffix(int i, int j) {
    int u = n-j+1, v = n-i+1;
    return suffix[v] - suffix[u-1] * pw[v-u+1];
}
void push(Palin T) {
    pre[T.l-1].push_back(T);
    suf[T.r+1].push_back(T);
}
int binary_search(int x, int y) {
    int lo = 0, hi = min(x, n-y+1), rz = 0;
    while (lo <= hi) {
        int mid=lo+hi>>1;
        if (get_prefix(x-mid+1, x) == get_suffix(y, y+mid-1)) {
            rz = mid;
            lo = mid+1;
        } else hi = mid-1;
    }
    return rz;
}
int main() {
    ios::sync_with_stdio(0);
    cin >> w;
    n = w.size();
    w = ' ' + w;
    w = w + ' ';
    pw[0] = 1;
    FORN(i, 1, n) pw[i] = pw[i-1] * 29;
    FORN(i, 1, n) prefix[i] = prefix[i-1] * 29 + w[i] - 'a' + 1;
    FORD(i, n, 1) suffix[n-i+1] = suffix[n-i] * 29 + w[i] - 'a' + 1;
    m = 0;
    FORN(i, 1, n) {
        int rz = binary_search(i, i);
        ++m;
        palin[m] = {i-rz+1, i+rz-1, 1};
        if (w[i] == w[i+1]) {
            ++m;
            rz = binary_search(i, i+1);
            palin[m] = {i-rz+1, i+rz, 0};
        }
    }
    FORN(i, 1, m) {
        palin[i].update();
        push(palin[i]);
        result += palin[i].size;
    }
    FORN(i, 1, n) {
        subt[i] += subt[i-1];
        ad[i] += ad[i-1];
        su[i] += su[i-1];
    }
    FORN(i, 1, n) subt[i] += ad[i] * i + (-i) * su[i];
    long long cur = result;
    FORN(i, 1, n) {
        FORN(ch, 'a', 'z') if (ch != w[i]) {
            long long cur_ch = 0;
            if (ch == w[i-1]) cur_ch += 1 + binary_search(i-2, i+1);
            if (ch == w[i+1]) cur_ch += 1 + binary_search(i-1, i+2);
            //if (i==2 && ch == 'c') cout << cur_ch << '\n';
            for(auto ss: pre[i]) 
                if (w[ss.r+1] == ch) cur_ch += 1+ binary_search(i-1, ss.r+2); 
            for(auto ss: suf[i]) 
                if (w[ss.l-1] == ch) cur_ch += 1 + binary_search(ss.l-2, i+1);
            result = max(result, cur - subt[i] + cur_ch);
        }
    }
    cout << result;
    return 0;
}

Compilation message

palinilap.cpp: In member function 'void Palin::update()':
palinilap.cpp:23:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         m = l + r >> 1;
             ~~^~~
palinilap.cpp: In function 'int binary_search(int, int)':
palinilap.cpp:46:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=lo+hi>>1;
                 ~~^~~

Subtask #1
17.0 / 17.0

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

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6008 KB Output is correct
2 Correct 10 ms 6008 KB Output is correct
3 Correct 11 ms 5880 KB Output is correct
4 Correct 9 ms 5496 KB Output is correct
5 Correct 12 ms 5752 KB Output is correct
6 Correct 11 ms 5880 KB Output is correct
7 Correct 10 ms 5752 KB Output is correct

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 21116 KB Output is correct
2 Correct 91 ms 24184 KB Output is correct
3 Correct 91 ms 24236 KB Output is correct
4 Correct 118 ms 19868 KB Output is correct
5 Correct 110 ms 19916 KB Output is correct
6 Correct 108 ms 19740 KB Output is correct
7 Correct 105 ms 19868 KB Output is correct
8 Correct 74 ms 24108 KB Output is correct
9 Correct 105 ms 19868 KB Output is correct
10 Correct 105 ms 19868 KB Output is correct
11 Correct 95 ms 24104 KB Output is correct
12 Correct 120 ms 25500 KB Output is correct
13 Correct 108 ms 20856 KB Output is correct
14 Correct 120 ms 20508 KB Output is correct
15 Correct 117 ms 20908 KB Output is correct
16 Correct 102 ms 24136 KB Output is correct
17 Correct 87 ms 18200 KB Output is correct
18 Incorrect 101 ms 20236 KB Output isn't correct
19 Halted 0 ms 0 KB -