fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. #define ld long double
  4. #define ll long long int
  5. #define float long double
  6. #define pb push_back
  7. #define mk make_pair
  8. #define mod 1000000007
  9. #define ALL(a) a.begin(),a.end()
  10. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  11. #define DEBUG(x) cout<<" x is "<<x<<"\n"
  12. using namespace std;
  13.  
  14. //inline size_t key( int a,int b,int c,int d) {return a*b*c*d-7707;}
  15. //unordered_map<size_t,bool >vismap;
  16.  
  17.  
  18. /*int dx[] = {1,-1,0,0} , dy[] = {0,0,1,-1}; */  // 2 Direction
  19. /*int dx[] = {1,0} , dy[] = {0,1};     */  // 4 Direction
  20. /* int dx[] = {1,-1,0,0,1,1,-1,-1} , dy[] = {0,0,1,-1,1,-1,1,-1}; */ // 8 Direction
  21. /* int dx[] = {1,-1,1,-1,2,2,-2,-2} , dy[] = {2,2,-2,-2,1,-1,1,-1}; */ // Knight Direction
  22. /* int dx[] = {2,-2,1,1,-1,-1} , dy[] = {0,0,1,-1,1,-1}; */ // Hexagonal Direction
  23.  
  24. ll S,M,SM,MS,SMS;
  25. string s;
  26.  
  27. const ll N=1000000+10;
  28. const ll  sqN=320;
  29. int ans[N];
  30.  
  31.  
  32.  
  33. struct query{
  34.     ll l;
  35.     ll r;
  36.     ll idx;
  37. } Q[N];
  38.  
  39.  
  40. bool comp(query &q1,query &q2){
  41.     if(q1.l/sqN !=q2.l/sqN){
  42.         return q1.l <q2.l;
  43.     }
  44.     if((q1.l/sqN) &1){
  45.         return q1.r <q2.r;
  46.     }
  47.     return q1.r>q2.r;
  48. }
  49.  
  50.  
  51. inline void addFront(ll i){
  52.     if(s[i]=='s'){
  53.         SMS+=MS;
  54.         SM+=M;
  55.         S++;
  56.     }
  57.     else if(s[i]=='m'){
  58.         MS+=S;
  59.         M++;
  60.     }
  61. }
  62.  
  63. inline void addRear(ll i){
  64.     if(s[i]=='s'){
  65.         SMS+=SM;
  66.         S++;
  67.         MS+=M;
  68.     }
  69.  
  70.     else if(s[i]=='m'){
  71.         SM+=S;
  72.         M++;
  73.     }
  74. }
  75.  
  76. inline void remFront(ll i){
  77.       if(s[i]=='s'){
  78.         SMS-=MS;
  79.         SM-=M;
  80.         S--;
  81.     }
  82.     else if(s[i]=='m'){
  83.         MS-=S;
  84.         M--;
  85.     }
  86. }
  87.  
  88. inline void remRear(ll i){
  89.     if(s[i]=='s'){
  90.         SMS-=SM;
  91.         S--;
  92.         MS-=M;
  93.     }
  94.     else if(s[i]=='m'){
  95.         SM-=S;
  96.         M--;
  97.     }
  98. }
  99.  
  100.  
  101.  
  102. int main(){
  103.     fast
  104.  
  105.    cin>>s;
  106.  
  107.     ll q,l,r;
  108.     cin>>q;
  109.     for(ll i=0;i<q;i++){
  110.         cin>>l>>r;
  111.  
  112.         l--;r--;
  113.         Q[i].l=l;
  114.         Q[i].r=r;
  115.         Q[i].idx=i;
  116.     }
  117.  
  118.     sort(Q,Q+q,comp);
  119.  
  120.     l=0,r=-1;
  121.  
  122.     for(ll i=0;i<q;i++){
  123.  
  124.         ll L=Q[i].l;
  125.         ll R=Q[i].r;
  126.         if(L>R){
  127.             ans[Q[i].idx]=0;
  128.             continue;
  129.         }
  130.         while(l<L){
  131.             remFront(l);
  132.             l++;
  133.         }
  134.  
  135.         while(l>L){
  136.             l--;
  137.             addFront(l);
  138.         }
  139.  
  140.         while(r<R){
  141.             r++;
  142.             addRear(r);
  143.         }
  144.  
  145.         while(r>R){
  146.             remRear(r);
  147.             r--;
  148.         }
  149.  
  150.         ans[Q[i].idx]=SMS;
  151.  
  152.     }
  153.  
  154.     for(ll i=0;i<q;i++){
  155.         cout<<ans[i]<<"\n";
  156.     }
  157.  
  158.  
  159.  
  160.     return 0;
  161. }
  162.  
Success #stdin #stdout 0s 4500KB
comments (?)
stdin
copy 
sasmasamsas

3

1 6

3 9

8 11
stdout
copy 
2
4
0
https://ideone.com/Z7Wuea
language:
C++14 (clang 8.0)
created:
6 years ago
visibility:
secret

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!