fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //
  4. #pragma GCC optimize("O3,unroll-loops")
  5. #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  6. //
  7. const int maxn = 1e5 + 5;
  8. const short int S = 320;
  9. //
  10. int n, q;
  11. long long A[maxn], diff[S][maxn];
  12. //
  13. void process (void)
  14. {
  15.     cin >> n >> q;
  16.     for (int l, r, d; q--;)
  17.     {
  18.         cin >> l >> r >> d;
  19.         if (d < S)
  20.         {
  21.             int k = (r - l) / d + 1;
  22.             //
  23.             ++diff[d][l];
  24.             if (r + d <= n)
  25.                 diff[d][r + d] -= k + 1;
  26.             if (r + d * 2 <= n)
  27.                 diff[d][r + d * 2] += k;
  28.         }
  29.         else
  30.             for (int j = 1, i = l; i <= r; i += d, ++j)
  31.                 A[i] += j;
  32.     }
  33.  
  34.     for (int d = 1; d < S; ++d)
  35.     {
  36.         for (int i = d + 1; i <= n; ++i)
  37.         {
  38.             diff[d][i] += diff[d][i - d];
  39.             if (i > d * 2)
  40.                 diff[d][i - d] += diff[d][i - d * 2];
  41.         }
  42.         for (int i = max(d, n - d) + 1; i <= n; ++i)
  43.             diff[d][i] += diff[d][i - d];
  44.         for (int i = 1; i <= n; ++i)
  45.             A[i] += diff[d][i];
  46.     }
  47.  
  48.     for (int i = 1; i <= n; ++i)
  49.         cout << A[i] << ' ';
  50. }
  51. //
  52. signed main (void)
  53. {
  54.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  55.     process();
  56. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/5LGeZT
https://m...content-available-to-author-only...j.com/problem/259
language:
C++14 (gcc 8.3)
created:
18 hours 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!