fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. #pragma GCC optimize("O2")
  4. #pragma GCC optimize("O3")
  5. #pragma GCC optimize("Ofast")
  6.  
  7. #define int long long
  8.  
  9. #define pii pair<int,int>
  10. #define ii int,int
  11. #define fi first
  12. #define se second
  13. #define pb push_back
  14. #define lb lower_bound
  15. #define ub upper_bound
  16. #define umap unordered_map
  17. #define BIT(mask, i) ((mask >> i)&1)
  18. #define ALL(c) c.begin(), c.end()
  19.  
  20. using namespace std;
  21.  
  22. mt19937 rd(chrono::high_resolution_clock::now().time_since_epoch().count());
  23. int rand(int l, int r){
  24.     return  l + rd()*rd()%(r-l+1);
  25. }
  26.  
  27. const int N = 1e6+7;
  28. const int M = 1e3+3;
  29. const int MOD = 1e9+7;
  30. const int inf = 3e18;
  31.  
  32. int n, q, a[N], r;
  33. int pos[N]; // pos[i] = số camera quét qua i
  34.  
  35. void sub1(){ // Bruteforce
  36.     for(int i = 1; i <= q; i++){
  37.         for(int j = max(a[i] - r, 1*1ll); j <= min(a[i] + r, n); j++){
  38.             pos[j]++; // đánh dấu camera thứ i quét qua pos[j]
  39.         }
  40.     }
  41.     for(int i = 1; i <= n; i++){
  42.         cout << pos[i] << ' ';
  43.     }
  44. }
  45.  
  46. void sub2(){ // Sử dụng mảng tổng tiền tố
  47.     for(int i = 1; i <= q; i++){ // duyệt tất cả các camera
  48.         int l = max(a[i] - r, 1*1ll);
  49.         int R = min(a[i] + r, n);
  50.         pos[l]++;
  51.         pos[R+1]--;
  52.     }
  53.     for(int i = 1; i <= n; i++){
  54.         pos[i] += pos[i-1];
  55.     }
  56.     for(int i = 1; i <= n; i++) cout << pos[i] << ' ';
  57. }
  58.  
  59. void solve(){
  60.     cin >> n >> q >> r;
  61.     for(int i = 1; i <= q; i++){
  62.         cin >> a[i];
  63.     }
  64.     sub2();
  65. }
  66.  
  67. signed main(){
  68.     ios_base::sync_with_stdio(0);
  69.     cin.tie(0);
  70.     cout.tie(0);
  71.     solve();
  72. }
  73.  
  74.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cw0yTz
language:
C++14 (gcc 8.3)
created:
7 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!