fork download
copy 
  1. // ROOT : DRAGON3012009
  2. #include <bits/stdc++.h>
  3. #define ll long long
  4. #define ld long double
  5. #define el "\n"
  6. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  7. #define __ROOT__ int main()
  8. #pragma GCC optimize("O2")
  9. //#pragma GCC optimize("unroll-loops")
  10. //#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
  11. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  12. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  13. #define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
  14. #define fi first
  15. #define se second
  16. #define M 1000000007
  17. #define MAXN 200001
  18. #define INF (1ll<<30)
  19. #define BLOCK_SIZE 425
  20. #define MAX_NODE 1001001
  21. #define LOG 19
  22. #define ALPHA_SIZE 26
  23. #define BASE 256
  24. #define NAME "file"
  25. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end());
  26. using namespace std;
  27. using namespace chrono ;
  28. const ll MOD[] = {(ll)1e9 + 2277, (ll)1e9 + 5277, (ll)1e9 + 8277, (ll)1e9 + 9277, (ll) 1e9 + 7 };
  29. const ll NMOD = 1;
  30. const int dx[] = {-1, 0, 1,0};
  31. const int dy[] = {0, 1, 0, -1};
  32. //**Variable**//
  33. ll n, q  ;
  34. ll arr[MAXN];
  35. //**Struct**//
  36. struct Seg {
  37.     ll val[MAXN << 2 ] ;
  38.     void update(ll id, ll l, ll r, ll pos, ll value  ) {
  39.         if(l == r ) val[id] = value ;
  40.         else {
  41.             ll m = l + r >> 1 ;
  42.             if(m >= pos ) update(id << 1, l, m, pos,value) ;
  43.             else update(id << 1|1, m + 1, r, pos, value) ;
  44.             val[id] = max(val[id << 1], val[id << 1 | 1 ]) ;
  45.         }
  46.     }
  47.     ll find_pos(ll id, ll l, ll r, ll u, ll v, ll value ) {
  48.         if(val[id] < value || u > r || v < l ) return -1 ;
  49.         if(l == r ) return l ;
  50.         ll ans = -1 ;
  51.         ll m = l + r >> 1;
  52.         if(val[id << 1 ] >= value ) ans = find_pos(id << 1, l, m, u, v, value) ;
  53.         if(ans != -1 ) return ans ;
  54.         if(val[id << 1 | 1 ] >= value ) ans = find_pos(id << 1 | 1, m + 1, r, u, v, value ) ;
  55.         return ans;
  56.     }
  57. } seg;
  58. //**Function**//
  59. template<class X, class Y >
  60. bool minimize(X & x, const Y &y ) {
  61.     return x > y ? x = y, 1:0 ;
  62. }
  63. template<class X, class Y >
  64. bool maximize(X &x, const Y &y ) {
  65.     return x < y ? x = y, 1:0 ;
  66. }
  67.  
  68. void init() {
  69.     cin>>n >> q ;
  70.     FOR(i,1, n) cin >> arr[i] ;
  71.     FOR(i, 1, n  ) seg.update(1, 1, n, i, arr[i]) ;
  72. }
  73.  
  74. void solve() {
  75.     FOR(i, 1,  q ) {
  76.         ll l, r, x ;
  77.         cin >> l >> r >> x ;
  78.         ll cur = l  ;
  79.         while(cur <= r ) {
  80.             ll p = seg.find_pos(1, 1, n, cur, r, x) ;
  81.             if(p == - 1 ) break ;
  82.             arr[p] %= x ;
  83.             seg.update(1, 1, n, p, arr[p]) ;
  84.             cur = p + 1 ;
  85. //            cout << p << " " ;
  86.         }
  87. //        cout << " run " << el ;
  88.     }
  89.     FOR(i, 1, n  )cout << arr[i] << " " ;
  90. }
  91.  
  92. __ROOT__ {
  93.     // freopen(NAME".inp" , "r" , stdin);
  94.     // freopen(NAME".out" , "w", stdout) ;
  95.     fast;
  96.     int t = 1; // cin >> t ;
  97.     while(t--) {
  98.         init();
  99.         solve();
  100.     }
  101.     return (0&0);
  102. }
  103.  
  104.  
  105.  
  106.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zG6tpD
language:
C++14 (gcc 8.3)
created:
4 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!