fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int a[2000007], temp[2000007], seg[4000007];
  5.  
  6. int maketree(int low, int high, int pos,int array[])
  7. {
  8.     if(low == high) 
  9.     {
  10.         seg[low] = temp[low];
  11.         return 0;
  12.     }
  13.  
  14.     int mid = (low + high) / 2;
  15.  
  16.     maketree(low, mid, pos*2 + 1, array);
  17.     maketree(mid + 1, high, pos * 2 + 2, array);
  18.  
  19.     seg[pos] = max(seg[2* pos + 1], seg[2 * pos + 2]);
  20. }
  21.  
  22. int query(int low, int high, int qlow, int qhigh, int pos)
  23. {
  24.     if(qlow <= low && high <= qhigh)
  25.         return seg[pos];
  26.  
  27.     if(qlow > high || qhigh < low)
  28.         return INT_MIN;
  29.  
  30.     int mid = (low + high) / 2;
  31.  
  32.     return max(query(low, mid, qlow, qhigh, pos*2 + 1), query(mid + 1, high, qlow, qhigh, pos * 2 + 2));
  33. }
  34.  
  35. int main()
  36. {
  37.     int n, k, p, cnt = 0;
  38.  
  39.     cin>>n>>k>>p;
  40.  
  41.     memset(a, 0, sizeof(a));
  42.  
  43.     for(int i = 0; i < n; i++)
  44.     {
  45.         cin>>a[i];
  46.  
  47.         if(a[i] == 1)
  48.             cnt++;
  49.  
  50.         a[i + n] = a[i];
  51.     }
  52.  
  53.     temp[2*n] = 0;
  54.     for(int i = 2 * n - 1; i >= 0; i--)
  55.         temp[i] = temp[i + 1] - a[i + k] + a[i]; 
  56.  
  57.     maketree(0, 2 * n - 1, 0, temp);
  58.  
  59.     string s;
  60.  
  61.     cin>>s;
  62.  
  63.     int size = s.length(), start = n;
  64.  
  65.     for(int i = 0; i < size; i++)
  66.     {
  67.         if(s[i] == '!')
  68.         {
  69.             start = start - 1;
  70.             if(start == 0) start = n;
  71.         }
  72.         else 
  73.         {
  74.             if(k >= n) 
  75.                 cout<<cnt<<"\n";
  76.             else
  77.             {
  78.                 int ans = query(0, 2 * n - 1, start, min(2 * n -1, start + k - 1), 0);
  79.  
  80.                 cout<<ans<<"\n";
  81.             }
  82.         }
  83.     }
  84.  
  85.     return 0;
  86. }
  87.  
Success #stdin #stdout 0s 46480KB
comments (?)
stdin
copy 
5 3 4
1 0 0 1 1
?!!?
stdout
copy 
0
0
https://ideone.com/5xdql7
language:
C++14 (gcc 8.3)
created:
6 years 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!