fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ii;
  4. ii ar[1000000],sum[1000000],vihu[1000000];
  5.  
  6. int main()
  7. {
  8.    ii n,k,p,i;
  9.    string s;
  10.    cin>>n>>k>>p;
  11.    k=min(k,n);
  12.    for(i=1;i<=n;i++)
  13.    {
  14.        cin>>ar[i];
  15.        ar[i+n]=ar[i];
  16.    }
  17.    cin>>s;
  18.    for(i=1;i<=k;i++)
  19.    {
  20.        sum[i]=sum[i-1]+ar[i];
  21.    }
  22.    for(i=k+1;i<=2*n;i++)
  23.    {
  24.        sum[i]=sum[i-1]+ar[i]-ar[i-k];
  25.    }
  26.        /*     for(i=1;i<=2*n;i++)
  27.               cout<<sum[i]<<" ";
  28.                  cout<<endl;*/
  29.     deque<ii> dq;
  30.     for(i=k;i<=n;i++)
  31.     {
  32.         while(!dq.empty()&&sum[i]>=sum[dq.back()])
  33.             dq.pop_back();
  34.         dq.push_back(i);
  35.     }
  36.     vihu[1]=dq.front();
  37.     for(i=n+1;i<2*n;i++)
  38.     {
  39.        while(!dq.empty()&&dq.front()<=(i-n))
  40.         dq.pop_front();
  41.        while(!dq.empty()&&sum[i]>=sum[dq.back()])
  42.         dq.pop_back();
  43.        dq.push_back(i);
  44.        vihu[i-n+1]=dq.front();
  45.     }
  46.    ii u=1;
  47.    for(i=0;i<p;i++)
  48.    {
  49.        if(s[i]=='?'){
  50.         cout<<sum[vihu[u]]<<endl;
  51.        }
  52.        else
  53.        {
  54.          u++;
  55.          u%=n;
  56.        }
  57.    }
  58.    return 0;
  59. }
  60.  
Success #stdin #stdout 0s 26320KB
comments (?)
stdin
copy 
5 5 4
1 0 0 1 1
?!!?
stdout
copy 
3
3
https://ideone.com/3R8eHq
language:
C++ 4.3.2 (gcc-4.3.2)
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!