oj.uz

Submission #131901

# Submission time Handle Problem Language Result Execution time Memory
131901 2019-07-18T02:01:08 Z letrongdat Palinilap (COI16_palinilap) C++17
54 / 100
 118 ms 25372 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];
int get_prefix(int i, int j) {
    return prefix[j] - prefix[i-1] * pw[j-i+1];
}
int 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]) {
            int 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);
            //cout << i << ' ' << char(ch) << ' ' << -subt[i] << ' ' << cur_ch << '\n';
            result = max(result, cur - subt[i] + cur_ch);
            //cout << i << ' ' << char(ch) << change << '\n';
        }
    }
    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 10 ms 6136 KB Output is correct
2 Correct 10 ms 6136 KB Output is correct
3 Correct 10 ms 5880 KB Output is correct
4 Correct 9 ms 5496 KB Output is correct
5 Correct 11 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 110 ms 21288 KB Output is correct
2 Correct 88 ms 24208 KB Output is correct
3 Correct 86 ms 24232 KB Output is correct
4 Correct 107 ms 19984 KB Output is correct
5 Correct 106 ms 19868 KB Output is correct
6 Correct 106 ms 19868 KB Output is correct
7 Correct 108 ms 19996 KB Output is correct
8 Correct 76 ms 24244 KB Output is correct
9 Correct 106 ms 19996 KB Output is correct
10 Correct 108 ms 20012 KB Output is correct
11 Correct 88 ms 24232 KB Output is correct
12 Correct 110 ms 25372 KB Output is correct
13 Correct 94 ms 21064 KB Output is correct
14 Correct 104 ms 20608 KB Output is correct
15 Correct 118 ms 20888 KB Output is correct
16 Incorrect 107 ms 24132 KB Output isn't correct
17 Halted 0 ms 0 KB -