oj.uz

답안 #652668

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
652668 2022-10-23T17:17:53 Z caccaccac Palinilap (COI16_palinilap) C++14
54 / 100
 99 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 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] * 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) {
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Correct 3 ms 5064 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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 6664 KB Output is correct
2 Correct 6 ms 6584 KB Output is correct
3 Correct 6 ms 6356 KB Output is correct
4 Correct 6 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 6 ms 5972 KB Output is correct

Subtask #3
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 30412 KB Output is correct
2 Correct 56 ms 35836 KB Output is correct
3 Correct 55 ms 35880 KB Output is correct
4 Correct 76 ms 28116 KB Output is correct
5 Correct 77 ms 27992 KB Output is correct
6 Correct 95 ms 27928 KB Output is correct
7 Correct 75 ms 28144 KB Output is correct
8 Correct 49 ms 35920 KB Output is correct
9 Correct 74 ms 28012 KB Output is correct
10 Correct 77 ms 28096 KB Output is correct
11 Correct 77 ms 35868 KB Output is correct
12 Correct 73 ms 36164 KB Output is correct
13 Correct 76 ms 30472 KB Output is correct
14 Correct 99 ms 28916 KB Output is correct
15 Correct 79 ms 29512 KB Output is correct
16 Correct 61 ms 35360 KB Output is correct
17 Correct 56 ms 23788 KB Output is correct
18 Incorrect 87 ms 27888 KB Output isn't correct
19 Halted 0 ms 0 KB -