Sahil_1327's blog

By Sahil_1327, history, 12 months ago, In English

https://codeforces.com/contest/245/submission/208958601 soln link // https://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){ // ans+=cnt[] // } } } signed main(){ IOS ll t=1; while(t--) solve(); return 0; }
  • Vote: I like it
  • +10
  • Vote: I do not like it

»
12 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
Code
»
12 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Auto comment: topic has been updated by Sahil_1327 (previous revision, new revision, compare).

»
12 months ago, # |
Rev. 2   Vote: I like it +20 Vote: I do not like it

Use '\n' instead of endl. Your code will get accepted.