fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. const int MAXN = 100005;
  7. const int SQRT_N = 317; // Pierwiastek z 100 000
  8.  
  9. int ans[MAXN];
  10. int diff[MAXN + SQRT_N]; // Tablica różnicowa dla małych d
  11.  
  12. struct Op {
  13.     int a, l;
  14. };
  15.  
  16. vector<Op> small_ops[SQRT_N];
  17.  
  18. int main() {
  19.     // Szybkie wejście/wyjście
  20.     ios_base::sync_with_stdio(false);
  21.     cin.tie(NULL);
  22.  
  23.     int n, k;
  24.     if (!(cin >> n >> k)) return 0;
  25.  
  26.     for (int i = 0; i < k; ++i) {
  27.         int a, l, d;
  28.         cin >> a >> l >> d;
  29.  
  30.         if (d >= SQRT_N) {
  31.             // Dla dużych kroków wykonujemy operację bezpośrednio
  32.             for (int j = 0; j < l; ++j) {
  33.                 ans[a + j * d]++;
  34.             }
  35.         } else {
  36.             // Dla małych kroków zapamiętujemy operację do późniejszego przetworzenia
  37.             small_ops[d].push_back({a, l});
  38.         }
  39.     }
  40.  
  41.     // Przetwarzamy małe kroki grupami dla każdego d
  42.     for (int d = 1; d < SQRT_N; ++d) {
  43.         if (small_ops[d].empty()) continue;
  44.  
  45.         // Czyścimy tablicę różnicową (tylko niezbędny zakres)
  46.         for (int i = 0; i <= n + d; ++i) diff[i] = 0;
  47.  
  48.         for (auto &op : small_ops[d]) {
  49.             diff[op.a]++;
  50.             // Kończymy dodawanie po l elementach
  51.             int end_pos = op.a + op.l * d;
  52.             if (end_pos <= n + d) {
  53.                 diff[end_pos]--;
  54.             }
  55.         }
  56.  
  57.         // Obliczamy sumy prefiksowe z krokiem d
  58.         for (int i = 1; i <= n; ++i) {
  59.             if (i > d) diff[i] += diff[i - d];
  60.             ans[i] += diff[i];
  61.         }
  62.     }
  63.  
  64.     // Wypisujemy wynik
  65.     for (int i = 1; i <= n; ++i) {
  66.         cout << ans[i] << (i == n ? "" : " ");
  67.     }
  68.     cout << endl;
  69.  
  70.     return 0;
  71. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
8 3
3 4 1
2 3 3
3 2 2
stdout
copy 
0 1 2 1 3 1 0 1
https://ideone.com/kEJi6e
language:
C++14 (gcc 8.3)
created:
1 day 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!