Advertisement
AbdeltwabMF

B. Troynacci Query

Jul 2nd, 2022
962
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.13 KB | None
  1. #include<bits/stdc++.h>
  2. #include<ext/pb_ds/assoc_container.hpp>
  3. #include<ext/pb_ds/tree_policy.hpp>
  4. using namespace __gnu_pbds;
  5. using namespace std;
  6. #define Foreach(i, c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
  7. #define For(i,a,b) for(int (i)=(a);(i) < (b); ++(i))
  8. #define rof(i,a,b) for(int (i)=(a);(i) > (b); --(i))
  9. #define rep(i, c)   for(auto &(i) : (c))
  10. #define x     first
  11. #define y     second
  12. #define pb  push_back
  13. #define PB  pop_back()
  14. #define iOS  ios_base::sync_with_stdio
  15. #define mp(a,b) make_pair(a,b)
  16. #define sqr(a)  ((1LL * (a) * (a)))
  17. #define all(a)  a.begin() , a.end()
  18. #define error(x) cerr << #x << " = " << (x) <<endl                                                                
  19. #define Error(a,b) cerr<<"( "<<#a<<" , "<<#b<<" ) = ( "<<(a)<<" , "<<(b)<<" )\n";
  20. #define errop(a) cerr<<#a<<" = ( "<<((a).x)<<" , "<<((a).y)<<" )\n";
  21. #define coud(a,b) cout<<fixed << setprecision((b)) << (a)
  22. #define double long double
  23. typedef pair<int,int> pii;
  24. typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> os;
  25. typedef long long ll;
  26. const int maxn = 1e5 + 100, mod = 1e9 + 7;
  27. #define int ll
  28. int p[maxn], x[maxn], f[maxn],a,b,n,q;
  29. main(int argc,char ** argv){
  30.     iOS(false);
  31.     cin >> n >> q;
  32.     For(i,0,2)
  33.         cin >> f[i];
  34.     cin >> a >> b;
  35.     For(i,2,maxn)
  36.         f[i] = (1LL * a * f[i-2] + 1LL * b * f[i-1]) % mod;
  37.     For(i,0,n)
  38.         cin >> x[i];
  39.     while(q--){
  40.         int l,r;
  41.         cin >> l >> r;
  42.         -- l;
  43.         -- r;
  44.         if(l < r){
  45.             p[l] = (p[l] + f[0]) % mod;
  46.             p[l+1] = (p[l+1] + f[1])%mod;
  47.             p[l+1] = (1LL * p[l+1] + mod - 1LL * ((1LL * b * f[0])%mod))%mod;
  48.             p[r + 1] = (1LL * p[r+1] + mod - f[r - l + 1])%mod;
  49.             p[r + 2] = (1LL * p[r+2] + mod - 1LL * ((1LL * a * f[r-l])%mod))%mod;
  50.         }
  51.         else{
  52.             p[l] = (p[l] + f[0])%mod;
  53.             p[r+1] = (1LL * p[r+1] + mod - ((1LL * b * f[0])%mod))%mod;
  54.             p[r+2] = (1LL * p[r+2] + mod - 1LL * ((1LL * a * f[0])%mod))%mod;
  55.         }
  56.     }
  57.     For(i,0,n){
  58.         if(i > 1)
  59.             p[i] = (1LL * p[i] + a * p[i-2])%mod;
  60.         if(i)
  61.             p[i] = (1LL * p[i] + b * p[i-1])%mod;
  62.         x[i] = (p[i] + x[i])%mod;
  63.         cout << x[i];
  64.         if(i + 1 < n)
  65.             cout << ' ';
  66.     }
  67.     cout << endl;
  68. }
Advertisement
RAW Paste Data Copied
Advertisement