oj.uz

Submission #1078978

# Submission time Handle Problem Language Result Execution time Memory
1078978 2024-08-28T08:56:05 Z Neco_arc Palinilap (COI16_palinilap) C++17
54 / 100
 59 ms 25872 KB 
#include <bits/stdc++.h>
#ifdef LOCAL
#include <bits/debug.hpp>
#endif // LOCAL

#define ll long long
#define all(x) x.begin(), x.end()
#define Neco "Palinilap"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 2e5 + 7

using namespace std;

const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;

int n;
string s;
ll H[2][maxn], po[maxn];
ll P[maxn][26], Sum;

struct BIT {
    ll bit[maxn];

    void update(int l, int r, ll val) {
        for(   ; l < maxn; l += (l & -l)) bit[l] += val;
        for(++r; r < maxn; r += (r & -r)) bit[r] -= val;
    }

    ll get(int x, ll ans = 0) {
        for(; x > 0; x -= (x & -x)) ans += bit[x];
        return ans;
    }

} Tsiz, Tval;

bool same(int x, int y, int u, int v) {
    ll P1 = H[0][y] - H[0][x - 1] * po[y - x + 1];
    ll P2 = H[1][u] - H[1][v + 1] * po[v - u + 1];
    return P1 == P2;
}

int Find(int x, int u) {
    int l = 1, r = min(x, n - u + 1);
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(same(x - mid + 1, x, u, u + mid - 1)) l = mid + 1;
        else r = mid - 1;
    }
    return r;
}

void solve()
{

    cin >> s;
    n = s.size(), s = ' ' + s;

    fi(i, 1, n)  H[0][i] = H[0][i - 1] * base + s[i];
    fid(i, n, 1) H[1][i] = H[1][i + 1] * base + s[i];

    fi(i, 1, n) { /// odd len
        int len = Find(i, i); Sum += len;
        int l = i - len + 1, r = i + len - 1;

        Tsiz.update(l, i - 1, 1), Tsiz.update(i + 1, r, -1);
        Tval.update(l, i - 1, 1 - l), Tval.update(i + 1, r, r + 1);

        --l, ++r;
        if(1 <= l && r <= n) {
            int k = Find(l - 1, r + 1) + 1;
            P[l][s[r] - 'a'] += k, P[r][s[l] - 'a'] += k;
        }
    }

    fi(i, 1, n - 1) { /// even len
        int len = Find(i, i + 1); Sum += len;
        int l = i - len + 1, r = i + len;

        Tsiz.update(l, i, 1), Tsiz.update(i + 1, r, -1);
        Tval.update(l, i, 1 - l), Tval.update(i + 1, r, r + 1);

        --l, ++r;
        if(1 <= l && r <= n) {
            int k = Find(l - 1, r + 1) + 1;
            P[l][s[r] - 'a'] += k, P[r][s[l] - 'a'] += k;
        }
    }

    ll ans = Sum;
    fi(i, 1, n) {
        ll bad = Tsiz.get(i) * i + Tval.get(i);
        fi(t, 0, 25) ans = max(ans, Sum - bad + P[i][t]);
    }

    cout << ans;

}


int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen(Neco".inp", "r")) {
        freopen(Neco".inp", "r", stdin);
        freopen(Neco".out", "w", stdout);
    }

    po[0] = 1;
    fi(i, 1, maxn - 2) po[i] = po[i - 1] * base;

    int nTest = 1;
//    cin >> nTest;


    while(nTest--)
    {
        solve();
    }


    return 0;
}

Compilation message

palinilap.cpp: In function 'int main()':
palinilap.cpp:115:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         freopen(Neco".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
palinilap.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         freopen(Neco".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2140 KB Output is correct
2 Correct 1 ms 2140 KB Output is correct
3 Correct 1 ms 2148 KB Output is correct
4 Correct 1 ms 2140 KB Output is correct
5 Correct 1 ms 2140 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3160 KB Output is correct
2 Correct 4 ms 3164 KB Output is correct
3 Correct 4 ms 3164 KB Output is correct
4 Correct 3 ms 2648 KB Output is correct
5 Correct 4 ms 2904 KB Output is correct
6 Correct 4 ms 3260 KB Output is correct
7 Correct 3 ms 3164 KB Output is correct

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 25688 KB Output is correct
2 Correct 54 ms 25688 KB Output is correct
3 Correct 57 ms 25688 KB Output is correct
4 Correct 55 ms 25684 KB Output is correct
5 Correct 56 ms 25680 KB Output is correct
6 Correct 55 ms 25684 KB Output is correct
7 Correct 53 ms 25680 KB Output is correct
8 Correct 39 ms 5464 KB Output is correct
9 Correct 53 ms 25688 KB Output is correct
10 Correct 55 ms 25676 KB Output is correct
11 Correct 57 ms 25680 KB Output is correct
12 Correct 59 ms 25872 KB Output is correct
13 Correct 50 ms 25676 KB Output is correct
14 Correct 53 ms 25676 KB Output is correct
15 Correct 55 ms 25680 KB Output is correct
16 Correct 58 ms 25684 KB Output is correct
17 Correct 47 ms 25688 KB Output is correct
18 Incorrect 59 ms 25680 KB Output isn't correct
19 Halted 0 ms 0 KB -