fork download
copy 
  1.     #include <cstdio>
  2.     #include <cstring>
  3.     #include <algorithm>
  4.     #include <map>
  5.     using namespace std;
  6.  
  7.     typedef long long ll;
  8.     const int MAXN = 300000;
  9.  
  10.     int n, k;
  11.     int a[MAXN];
  12.     map<ll,int> table;
  13.  
  14.     ll go(int l, int r)
  15.     {
  16.     if (l>=r) return 0;
  17.     if (l+1 == r) return (max(a[l], a[r])%k == 0);
  18.     // O(n)
  19.     int m = l;
  20.     for (int i=l+1; i<=r; i++)
  21.     if (a[i] < a[m])
  22.     m = i;
  23.     else if (a[i]==a[m])
  24.     {
  25.     if (abs((l+r)/2 - m) > abs((l+r)/2 - i))
  26.     m = i;
  27.     }
  28.     ll ret = 0;
  29.     table.clear();
  30.     ll sum = 0;
  31.     table.insert(pair<ll, int>(0, 1));
  32.     for (int i=m-1; i>=l; i--)
  33.     {
  34.     sum+=a[i];
  35.     if (sum>=k) sum %= k;
  36.     if (table.find(sum) != table.end())
  37.     table[sum]++;
  38.     else
  39.     table.insert(pair<ll, int>(sum, 1));
  40.     }
  41.     sum = 0;
  42.     if (table.find(0) != table.end()) ret += table[0]-1;
  43.     for (int i=m+1; i<=r; i++)
  44.     {
  45.     sum += a[i];
  46.     if (sum>=k) sum%=k;
  47.     ll x = k - sum;
  48.     if (x==k) x=0;
  49.     if (table.find(x) != table.end()) ret += table[x];
  50.     }
  51.     ret += go(l, m-1) + go(m+1, r);
  52.     return ret;
  53.     }
  54.  
  55.     int main()
  56.     {
  57.     scanf("%d%d", &n, &k);
  58.     for (int i=0; i<n; i++)
  59.     scanf("%d", &a[i]);
  60.     ll ans = go(0, n-1);
  61.     printf("%lld\n", ans);
  62.     }
Success #stdin #stdout 0s 4040KB
comments (?)
stdin
copy 
5 8
7 5 3 8 2
stdout
copy 
3
https://ideone.com/S5fPvC
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 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!