https://mirror.codeforces.com/contest/245/submission/208958601 soln link //↵
https://mirror.codeforces.com/contest/245/problem/H problem link//↵
↵
~~~~~↵
↵
#pragma GCC optimize ("O3,unroll-loops")↵
#pragma GCC target ("avx2")↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define all(x) x.begin(),x.end()↵
#define ll long long↵
#define ld long double↵
#define pb push_back↵
#define tr(it,a) for(auto it=a.begin();it!=a.end();it++)↵
#define fo(i,n) for(int i=0;i<n;i++)↵
#define fop(i,x,n) for(int i=x;i<=n;i++)↵
#define forv(i,l,n) for(int i=l;i>=n;i--)↵
#define nl <<endl;↵
typedef pair<ll,ll> pl;↵
typedef vector<ll> vl;↵
typedef vector<bool> vb;↵
typedef vector<ld> vd;↵
typedef vector<string> vs;↵
#define inp(v, n) for(int i=0; i<n; ++i) cin >> v[i];↵
#define opt(v) for(auto x: v) cout << x << ' '; cout nl↵
const ll mod = 1000000007;↵
const ll N = 2e5+10;↵
#define IOS ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);↵
void solve(){↵
↵
string s;↵
cin>>s;↵
ll q;↵
cin>>q;↵
ll n=s.size();↵
bool dp[n+3][n+3];↵
fo(i,n+3){↵
fo(j,n+3){↵
dp[i][j]=false;↵
}↵
}↵
for(int l=n-1;l>=0;--l){↵
fo(r,n){↵
if(l>r) continue;↵
ll len=r-l+1;↵
if(len==1) dp[l][r]=true;↵
else if(len==2 && s[l]==s[r]) dp[l][r]=true;↵
else if(s[l]==s[r] && dp[l+1][r-1]){↵
dp[l][r]=true;↵
}↵
else{↵
dp[l][r]=false;↵
}↵
}↵
}↵
ll cnt[n+1][n+1];↵
fo(i,n+1){↵
fo(j,n+1){↵
cnt[i][j]=0;↵
}↵
}↵
fo(i,n){↵
ll sm=0;↵
for(int j=i;j<n;++j){↵
if(dp[i][j]){↵
sm++;↵
}↵
cnt[i][j]=sm;↵
}↵
}↵
fo(j,n){↵
fop(i,1,n-1){↵
cnt[i][j]=cnt[i-1][j]+cnt[i][j];↵
}↵
}↵
while(q--){↵
ll a,b;↵
cin>>a>>b;↵
ll ans=0;↵
a--;↵
b--;↵
↵
// fop(i,a,b){↵
// ans+=cnt[i][b];↵
// }↵
if(a==0)↵
ans=cnt[b][b];↵
else{↵
ans= cnt[b][b]-cnt[a-1][b];↵
}↵
cout<<ans<<endl;↵
// fop(j,a,b){****↵
↵
<spoiler summary="Spoiler">↵
...↵
</spoiler>↵
↵
****↵
// ans+=cnt[]↵
// }↵
}↵
}↵
signed main(){↵
IOS↵
ll t=1;↵
while(t--) solve();↵
return 0;↵
}↵
~~~~~
https://mirror.codeforces.com/contest/245/problem/H problem link//↵
↵
~~~~~↵
↵
#pragma GCC optimize ("O3,unroll-loops")↵
#pragma GCC target ("avx2")↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define all(x) x.begin(),x.end()↵
#define ll long long↵
#define ld long double↵
#define pb push_back↵
#define tr(it,a) for(auto it=a.begin();it!=a.end();it++)↵
#define fo(i,n) for(int i=0;i<n;i++)↵
#define fop(i,x,n) for(int i=x;i<=n;i++)↵
#define forv(i,l,n) for(int i=l;i>=n;i--)↵
#define nl <<endl;↵
typedef pair<ll,ll> pl;↵
typedef vector<ll> vl;↵
typedef vector<bool> vb;↵
typedef vector<ld> vd;↵
typedef vector<string> vs;↵
#define inp(v, n) for(int i=0; i<n; ++i) cin >> v[i];↵
#define opt(v) for(auto x: v) cout << x << ' '; cout nl↵
const ll mod = 1000000007;↵
const ll N = 2e5+10;↵
#define IOS ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);↵
void solve(){↵
↵
string s;↵
cin>>s;↵
ll q;↵
cin>>q;↵
ll n=s.size();↵
bool dp[n+3][n+3];↵
fo(i,n+3){↵
fo(j,n+3){↵
dp[i][j]=false;↵
}↵
}↵
for(int l=n-1;l>=0;--l){↵
fo(r,n){↵
if(l>r) continue;↵
ll len=r-l+1;↵
if(len==1) dp[l][r]=true;↵
else if(len==2 && s[l]==s[r]) dp[l][r]=true;↵
else if(s[l]==s[r] && dp[l+1][r-1]){↵
dp[l][r]=true;↵
}↵
else{↵
dp[l][r]=false;↵
}↵
}↵
}↵
ll cnt[n+1][n+1];↵
fo(i,n+1){↵
fo(j,n+1){↵
cnt[i][j]=0;↵
}↵
}↵
fo(i,n){↵
ll sm=0;↵
for(int j=i;j<n;++j){↵
if(dp[i][j]){↵
sm++;↵
}↵
cnt[i][j]=sm;↵
}↵
}↵
fo(j,n){↵
fop(i,1,n-1){↵
cnt[i][j]=cnt[i-1][j]+cnt[i][j];↵
}↵
}↵
while(q--){↵
ll a,b;↵
cin>>a>>b;↵
ll ans=0;↵
a--;↵
b--;↵
↵
// fop(i,a,b){↵
// ans+=cnt[i][b];↵
// }↵
if(a==0)↵
ans=cnt[b][b];↵
else{↵
ans= cnt[b][b]-cnt[a-1][b];↵
}↵
cout<<ans<<endl;↵
// fop(j,a,b){
↵
<spoiler summary="Spoiler">↵
...↵
</spoiler>↵
↵
****
// ans+=cnt[]↵
// }↵
}↵
}↵
signed main(){↵
IOS↵
ll t=1;↵
while(t--) solve();↵
return 0;↵
}↵
~~~~~
