Submission #531541

#TimeUsernameProblemLanguageResultExecution timeMemory
531541colazcyPalinilap (COI16_palinilap)C++17
100 / 100
164 ms24672 KiB
#include <cstdio> #include <cassert> #include <cstring> #include <utility> #include <algorithm> #define let const auto #define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++) #define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--) #define repn(lim) for(auto REPN_lIM = lim,REPN = 1;REPN <= REPN_lIM;REPN++) #define debug(...) fprintf(stderr,__VA_ARGS__) #define trace() debug("line : %d, Function : %s\n",__LINE__,__FUNCTION__) using ll = long long; constexpr int maxn = 1e5 +10; constexpr int lowbit(const int x){return x & (-x);} int n; char buf[maxn]; template <int base,int mod> struct Hash{ static int add(const int a,const int b){return a + b >= mod ? a + b - mod : a + b;} static int sub(const int a,const int b){return a >= b ? a - b : a - b + mod;} static int mul(const int a,const int b){return 1ll * a * b % mod;} int pw[maxn],sum[maxn],sum_rev[maxn]; void init(){ pw[0] = 1; rep(i,1,n)pw[i] = mul(pw[i - 1],base); rep(i,1,n)sum[i] = add(mul(sum[i - 1],base),buf[i]); per(i,n,1)sum_rev[i] = add(mul(sum_rev[i + 1],base),buf[i]); } int query(const int l,const int r){ return sub(sum[r],mul(sum[l - 1],pw[r - l + 1])); } int query_rev(const int l,const int r){ return sub(sum_rev[l],mul(sum_rev[r + 1],pw[r - l + 1])); } }; Hash<127,1000000000 + 7> ha; Hash<131,1000000000 + 9> hb; struct fenwick{ ll f[maxn]; void add(int pos,const ll v){ while(pos <= n + 1){ f[pos] += v; pos += lowbit(pos); } } ll query(int pos){ ll res = 0; while(pos){ res += f[pos]; pos -= lowbit(pos); } return res; } }fs,fsi; ll delta[maxn][26]; void modify(const int l,const int r,const int beg,const int delta){ if(l > r)return; fs.add(l,beg); fs.add(l + 1,delta - beg); fs.add(r + 1,-(r - l + 1) * delta - beg); fs.add(r + 2,(r - l) * delta + beg); fsi.add(l,1ll * l * beg); fsi.add(l + 1,1ll * (l + 1) * (delta - beg)); fsi.add(r + 1,1ll * (r + 1) * (-(r - l + 1) * delta - beg)); fsi.add(r + 2,1ll * (r + 2) * ((r - l) * delta + beg)); } ll query(const int p){ return 1ll * (p + 1) * fs.query(p) - fsi.query(p); } ll sum,mx; int main(){ // std::freopen("palinilap.in","r",stdin); // std::freopen("palinilap.out","w",stdout); std::scanf("%s",buf + 1); n = std::strlen(buf + 1); ha.init(); hb.init(); rep(i,1,n){ int l = 0,r = std::min(i - 1,n - i),ans = 0; while(l <= r){ let mid = (l + r) >> 1; if(std::make_pair(ha.query_rev(i - mid,i),hb.query_rev(i - mid,i)) == std::make_pair(ha.query(i,i + mid),hb.query(i,i + mid)))ans = mid,l = mid + 1; else r = mid - 1; } sum += ans + 1; rep(c,0,25) if(c != buf[i] - 'a') delta[i][c] += ans + 1; modify(i - ans,i,1,1); modify(i + 1,i + ans,ans,-1); if(i - ans != 1 && i + ans != n){ let t = ans; l = 0,r = std::min(i - t - 3,n - (i + t + 2)),ans = -1; while(l <= r){ let mid = (l + r) >> 1; if(std::make_pair(ha.query_rev(i - t - 2 - mid,i - t - 2),hb.query_rev(i - t - 2 - mid,i - t - 2)) == std::make_pair(ha.query(i + t + 2,i + t + 2 + mid),hb.query(i + t + 2,i + t + 2 + mid)))ans = mid,l = mid + 1; else r = mid - 1; } delta[i - t - 1][buf[i + t + 1] - 'a'] += ans + 2; delta[i + t + 1][buf[i - t - 1] - 'a'] += ans + 2; } } rep(i,1,n - 1){ if(buf[i] != buf[i + 1]){ int l = 0,r = std::min(i - 2,n - i - 2),ans = -1; while(l <= r){ let mid = (l + r) >> 1; if(std::make_pair(ha.query_rev(i - 1 - mid,i - 1),hb.query_rev(i - 1 - mid,i - 1)) == std::make_pair(ha.query(i + 2,i + 2 + mid),hb.query(i + 2,i + 2 + mid)))ans = mid,l = mid + 1; else r = mid - 1; } delta[i][buf[i + 1] - 'a'] += ans + 2; delta[i + 1][buf[i] - 'a'] += ans + 2; continue; } int l = 0,r = std::min(i - 1,n - i - 1),ans = 0; while(l <= r){ let mid = (l + r) >> 1; if(std::make_pair(ha.query_rev(i - mid,i),hb.query_rev(i - mid,i)) == std::make_pair(ha.query(i + 1,i + 1 + mid),hb.query(i + 1,i + 1 + mid)))ans = mid,l = mid + 1; else r = mid - 1; } sum += ans + 1; modify(i - ans,i,1,1); modify(i + 1,i + 1 + ans,ans + 1,-1); if(i - ans != 1 && i + 1 + ans != n){ let t = ans; l = 0,r = std::min(i - ans - 3,n - (i + ans + 3)),ans = -1; while(l <= r){ let mid = (l + r) >> 1; if(std::make_pair(ha.query_rev(i - t - 2 - mid,i - t - 2),hb.query_rev(i - t - 2 - mid,i - t - 2)) == std::make_pair(ha.query(i + t + 3,i + t + 3 + mid),hb.query(i + t + 3,i + t + 3 + mid)))ans = mid,l = mid + 1; else r = mid - 1; } delta[i - t - 1][buf[i + t + 2] - 'a'] += ans + 2; delta[i + t + 2][buf[i - t - 1] - 'a'] += ans + 2; } } rep(i,1,n) rep(c,0,25) if(c != buf[i] - 'a') mx = std::max(mx,delta[i][c] - query(i)); std::printf("%lld\n",sum + mx); std::fclose(stdin); std::fclose(stdout); return 0; }

Compilation message (stderr)

palinilap.cpp: In function 'int main()':
palinilap.cpp:80:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |  std::scanf("%s",buf + 1);
      |  ~~~~~~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...