fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. #define int long long
  4.  
  5. #define debug     cout << "ok\n";
  6. #define SQR(x)    (1LL * ((x) * (x)))
  7. #define MASK(i)   (1LL << (i))
  8. #define BIT(x, i) (((x) >> (i)) & 1)
  9. #define fi        first
  10. #define se        second
  11. #define pb        push_back
  12.  
  13. #define mp make_pair
  14. #define pii pair<int,int>
  15. #define pli pair<ll,int>
  16. #define vi vector<int>
  17.  
  18. #define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  19.  
  20. typedef long long ll;
  21. typedef unsigned long long ull;
  22. typedef long double ld;
  23. typedef unsigned int ui;
  24.  
  25. using namespace std;
  26.  
  27. const int M = 1e9 + 7;
  28. const int INF = 1e9 + 7;
  29. const ll INFLL = (ll)2e18 + 7LL;
  30. const ld PI = acos(-1);
  31.  
  32. const int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
  33. const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1};
  34.  
  35. template<class _, class __>
  36.     bool minimize(_ &x, const __ y){
  37.         if(x > y){
  38.             x = y;
  39.             return true;
  40.         } else return false;
  41.     }
  42. template<class _, class __>
  43.     bool maximize(_ &x, const __ y){
  44.         if(x < y){
  45.             x = y;
  46.             return true;
  47.         } else return false;
  48.     }
  49.  
  50. template<class _,class __>
  51.     void Add(_ &x, const __ y) {
  52.         x += y;
  53.         if (x >= M) {
  54.             x -= M;
  55.         }
  56.         return;
  57.     }
  58.  
  59. template<class _,class __>
  60.     void Diff(_ &x, const __ y) {
  61.         x -= y;
  62.         if (x < 0) {
  63.             x += M;
  64.         }
  65.         return;
  66.     }
  67.  
  68. //--------------------------------------------------------------
  69.  
  70. const int MaxN = 3e5+7;
  71. const int S = 600;
  72.  
  73. int n,q,a[MaxN],res[MaxN],suma = 0,f[S+7];
  74. vector<pii> que[MaxN];
  75.  
  76. struct FenwickTree {
  77.     int Tr[MaxN];
  78.  
  79.     void Upd(int u,int v) {
  80.         for (; u < MaxN; u += u&-u) {
  81.             Tr[u]+=v;
  82.         }
  83.         return;
  84.     }
  85.  
  86.     int Get(int u) {
  87.         if (u < 0) return 0;
  88.         int res = 0;
  89.         for (; u; u -= u&-u) {
  90.             res += Tr[u];
  91.         }
  92.         return res;
  93.     }
  94. } Fw;
  95.  
  96.  
  97. int Query(int mod) {
  98.     if (mod > 3e5) return suma;
  99.     if (mod <= S) return f[mod];
  100.     int res = 0;
  101.     for (int i=0,j=0;j<=3e5;i++) {
  102.         int k = j + mod;
  103.         minimize(k,3e5+1);
  104.         res -= (Fw.Get(k-1) - Fw.Get(j-1)) * i * mod;
  105.         j = k;
  106.     }
  107.     res += suma;
  108.     return res;
  109. }
  110.  
  111. void sol() {
  112.     cin >> n >> q;
  113.     for (int i=1;i<=n;i++) cin >> a[i];
  114.     for (int i=1;i<=q;i++) {
  115.         int l,r,mod;
  116.         cin >> l >> r >> mod;
  117.         l++,r++;
  118.         que[l-1].pb(mp(mod,-i));
  119.         que[r].pb(mp(mod,i));
  120.     }
  121.     for (int i=1;i<=n;i++) {
  122.         suma += a[i];
  123.         for (int j=1;j<=S;j++) {
  124.             f[j] += a[i] % j;
  125.         }
  126.         Fw.Upd(a[i],1);
  127.         for (pii tmp : que[i]) {
  128.             int mod = tmp.fi;
  129.             int cs = abs(tmp.se);
  130.             int hs = cs / tmp.se;
  131.             res[cs] += hs * Query(mod);
  132.         }
  133.     }
  134.     for (int i=1;i<=q;i++) cout << res[i] << '\n';
  135. }
  136.  
  137. signed main() {
  138. //    freopen("test.inp","r",stdin);
  139. //    freopen("test.out","w",stdout);
  140.     FAST
  141.     int t=1;
  142. //    cin >> t;
  143.     while (t--) sol();
  144. }
  145.  
Success #stdin #stdout 0.01s 11768KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/b9iQZH
language:
C++14 (gcc 8.3)
created:
6 days 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!