oj.uz

답안 #652675

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
652675 2022-10-23T17:21:06 Z caccaccac Palinilap (COI16_palinilap) C++14
100 / 100
 118 ms 36328 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;
const long long MOD = 1e9 + 9277;
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] + MOD * MOD) % MOD;
}
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] + MOD * MOD) % MOD;
}
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 % MOD;
    FORN(i, 1, n) (prefix[i] = prefix[i-1] *311 + w[i] - 'a' + 1) %= MOD;
    FORD(i, n, 1) (suffix[n-i+1] = suffix[n-i] * 311  + w[i] - 'a' + 1) %= MOD;
    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:25:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |         m = l + r >> 1;
      |             ~~^~~
palinilap.cpp: In function 'long long int binary_search(long long int, long long int)':
palinilap.cpp:48:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |         long long mid=lo+hi>>1;
      |                       ~~^~~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 4 ms 5040 KB Output is correct
3 Correct 4 ms 5040 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 7 ms 6660 KB Output is correct
2 Correct 7 ms 6576 KB Output is correct
3 Correct 7 ms 6356 KB Output is correct
4 Correct 6 ms 5716 KB Output is correct
5 Correct 7 ms 5972 KB Output is correct
6 Correct 8 ms 6312 KB Output is correct
7 Correct 6 ms 5972 KB Output is correct

Subtask #3
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 110 ms 30568 KB Output is correct
2 Correct 76 ms 35924 KB Output is correct
3 Correct 72 ms 35972 KB Output is correct
4 Correct 97 ms 28056 KB Output is correct
5 Correct 98 ms 28024 KB Output is correct
6 Correct 101 ms 27864 KB Output is correct
7 Correct 98 ms 28148 KB Output is correct
8 Correct 63 ms 35836 KB Output is correct
9 Correct 118 ms 28016 KB Output is correct
10 Correct 101 ms 28068 KB Output is correct
11 Correct 72 ms 35836 KB Output is correct
12 Correct 102 ms 36328 KB Output is correct
13 Correct 92 ms 30440 KB Output is correct
14 Correct 103 ms 28908 KB Output is correct
15 Correct 98 ms 29516 KB Output is correct
16 Correct 89 ms 35420 KB Output is correct
17 Correct 73 ms 23724 KB Output is correct
18 Correct 112 ms 27968 KB Output is correct
19 Correct 78 ms 23724 KB Output is correct