oj.uz

Submission #652671

# Submission time Handle Problem Language Result Execution time Memory
652671 2022-10-23T17:19:25 Z caccaccac Palinilap (COI16_palinilap) C++14
54 / 100
 85 ms 36200 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 unsigned 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 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 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 7 ms 6576 KB Output is correct
2 Correct 8 ms 6576 KB Output is correct
3 Correct 6 ms 6228 KB Output is correct
4 Correct 5 ms 5716 KB Output is correct
5 Correct 6 ms 5972 KB Output is correct
6 Correct 7 ms 6228 KB Output is correct
7 Correct 7 ms 5972 KB Output is correct

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 30320 KB Output is correct
2 Correct 61 ms 35804 KB Output is correct
3 Correct 65 ms 35964 KB Output is correct
4 Correct 73 ms 28124 KB Output is correct
5 Correct 76 ms 27924 KB Output is correct
6 Correct 80 ms 27840 KB Output is correct
7 Correct 77 ms 28136 KB Output is correct
8 Correct 49 ms 35844 KB Output is correct
9 Correct 78 ms 27996 KB Output is correct
10 Correct 85 ms 28096 KB Output is correct
11 Correct 74 ms 35816 KB Output is correct
12 Correct 74 ms 36200 KB Output is correct
13 Correct 74 ms 30476 KB Output is correct
14 Correct 81 ms 28880 KB Output is correct
15 Correct 76 ms 29552 KB Output is correct
16 Correct 63 ms 35456 KB Output is correct
17 Correct 58 ms 23724 KB Output is correct
18 Incorrect 71 ms 27888 KB Output isn't correct
19 Halted 0 ms 0 KB -