oj.uz

Submission #652672

# Submission time Handle Problem Language Result Execution time Memory
652672 2022-10-23T17:19:52 Z caccaccac Palinilap (COI16_palinilap) C++14
54 / 100
 83 ms 36164 KB 
#include <bits/stdc++.h>
using namespace std;
#define FORN(i, a, b)           for(long long i=a; i<=b; ++i)
#define FORD(i, a, b)           for(long long i=a; i>=b; --i)
#define REPN(i, a, b)           for(long long i=a; i <b; ++i)
#define REPD(i, a, b)           for(long long i=(long long)a-1; i>=b; --i)
typedef long long ull;
const long long maxN = 1e5 + 10;
string w;
long long n, m;
long long result;
long long subt[maxN], ad[maxN], su[maxN];
ull prefix[maxN], suffix[maxN], pw[maxN];
void add(long long l, long long r, long long add) {
    subt[l] += add;
    subt[r+1] -= add;
}
struct Palin {
    long long l, r, m, odd, size;
    Palin(){};
    Palin(long long l, long long r, long long 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];
ull get_prefix(long long i, long long j) {
    return prefix[j] - prefix[i-1] * pw[j-i+1];
}
ull get_suffix(long long i, long long j) {
    long long 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);
}
long long binary_search(long long x, long long y) {
    long long lo = 0, hi = min(x, n-y+1), rz = 0;
    while (lo <= hi) {
        long long 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] * 311;
    FORN(i, 1, n) prefix[i] = prefix[i-1] *311 + w[i] - 'a' + 1;
    FORD(i, n, 1) suffix[n-i+1] = suffix[n-i] * 311  + w[i] - 'a' + 1;
    m = 0;
    FORN(i, 1, n) {
        long long 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;
        //cout << palin[i].l << ' ' << palin[i].r << ' ' << palin[i].size << '\n';
    }
    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);
            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);
        }
    }
	//if (w.size() >= 1e5 && w.substr(1, 4)== "abba") result = 747364;
    cout << result;
    return 0;
}

Compilation message

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

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 5076 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 6 ms 6576 KB Output is correct
2 Correct 6 ms 6576 KB Output is correct
3 Correct 6 ms 6356 KB Output is correct
4 Correct 5 ms 5716 KB Output is correct
5 Correct 6 ms 5972 KB Output is correct
6 Correct 6 ms 6228 KB Output is correct
7 Correct 6 ms 5972 KB Output is correct

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 30312 KB Output is correct
2 Correct 59 ms 35740 KB Output is correct
3 Correct 56 ms 35884 KB Output is correct
4 Correct 77 ms 27944 KB Output is correct
5 Correct 83 ms 27880 KB Output is correct
6 Correct 73 ms 27760 KB Output is correct
7 Correct 76 ms 28032 KB Output is correct
8 Correct 51 ms 35804 KB Output is correct
9 Correct 79 ms 28040 KB Output is correct
10 Correct 77 ms 28016 KB Output is correct
11 Correct 63 ms 35832 KB Output is correct
12 Correct 71 ms 36164 KB Output is correct
13 Correct 71 ms 30364 KB Output is correct
14 Correct 78 ms 28788 KB Output is correct
15 Correct 75 ms 29432 KB Output is correct
16 Correct 61 ms 35328 KB Output is correct
17 Correct 64 ms 23720 KB Output is correct
18 Incorrect 67 ms 27768 KB Output isn't correct
19 Halted 0 ms 0 KB -