fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. int N = 1e6 + 5;
  6. vector<bool> primes(N, true);
  7.  
  8. bool getBit(ll num,ll idx)
  9. {
  10.     return ((num>>idx)&1);
  11. }
  12.  
  13. void sieve()
  14. {
  15.     primes[0] = primes[1] = 0;
  16.     for (int i = 4; i < N; i += 2)
  17.     {
  18.         primes[i] = 0;
  19.     }
  20.     for (int i = 3; i * i < N; i += 2)
  21.     {
  22.         if (primes[i])
  23.         {
  24.             for (int j = i * i; j < N; j += i + i)
  25.             {
  26.                 primes[j] = 0;
  27.             }
  28.         }
  29.     }
  30. }
  31. int fixMod(char a,char b,int mod)
  32. {
  33.     return (((a-b)%mod)+mod)%mod;
  34. }
  35.  
  36. void solve()
  37. {
  38.     int N,Q;
  39.     string S;
  40.     cin>>N>>Q>>S;
  41.     S="@"+S;
  42.     string reff="doz";
  43.     vector<vector<ll>>prefix(3,vector<ll>(N+1));
  44.     for (int I=0;I<3;I++)
  45.     {
  46.         int counter=I;
  47.         for (int J=1;J<=N;J++)
  48.         {
  49.             prefix[I][J]=min({fixMod(S[J],reff[counter],26),fixMod(reff[counter],S[J],26)});
  50.             //cout<<fixMod(S[J],reff[counter],26)<<" "<<S[J]-'a'<<" "<<reff[counter]<<endl;
  51.             counter++;
  52.             counter%=3;
  53.         }
  54.         for (int J=1;J<=N;J++)
  55.         {
  56.             prefix[I][J]+=prefix[I][J-1];
  57.         }
  58.     }
  59.     for (int I=0;I<Q;I++)
  60.     {
  61.         int l,r;
  62.         cin>>l>>r;
  63.         if (r-l+1<3)
  64.         {
  65.             cout<<"0"<<endl;
  66.             continue;
  67.         }
  68.         int firstl=l%3,secondl=(l+1)%3,thirdl=(l+2)%3;
  69.         if (firstl==0)firstl=3;
  70.         if (secondl==0)secondl=3;
  71.         if (thirdl==0)thirdl=3;
  72.         firstl=l+(3-firstl);
  73.         secondl=l+(3-secondl);
  74.         thirdl=l+(3-thirdl);
  75.         int firstNumbers=(r-firstl+1)/3,secondNumbers=(r-secondl+1)/3,thirdNumbers=(r-thirdl+1)%3;
  76.         int firstr=firstl+(3*firstNumbers),secondr=secondl+(3*secondNumbers),thirdr=thirdl+(3*thirdNumbers);
  77.         int mx=max({firstNumbers,secondNumbers,thirdNumbers});
  78.         ll ans=0;
  79.         if ((firstr-firstl+1)/3==mx)ans=max(ans,prefix[0][firstr]-prefix[0][firstl-1]);
  80.         if ((secondr-secondl+1)/3==mx)ans=max(ans,prefix[1][secondr]-prefix[1][secondl-1]);
  81.         if ((thirdr-thirdl+1)/3==mx)ans=max(ans,prefix[2][thirdr]-prefix[2][thirdl-1]);
  82.         cout<<ans<<endl;
  83.     }
  84.     /*
  85.     ll l , r;
  86.     cin>>l>>r; l--;
  87.  
  88.     ll d1 = r/5 , d2 = l/5;
  89.     ll s1 = 5 * ((d1+1)*d1/2) , s2 = 5 * ((d2+1)*d2/2);
  90.     s1-= (4 - (r%5)) * d1;
  91.     s2-= (4 - (l%5)) * d2;
  92.     cout << s1 - s2 <<"\n";
  93.     */
  94. }
  95.  
  96. int main()
  97. {
  98.     ios::sync_with_stdio(0);
  99.     cin.tie(0);
  100.     cout.tie(0);
  101.  
  102.     int t = 1;
  103.     //cin >> t;
  104.  
  105.     while (t--)
  106.     {
  107.         solve();
  108.     }
  109.     return 0;
  110. }
  111.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Vaa83A
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!