fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6.  
  7. template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  8.  
  9. typedef long long int ll;
  10. typedef long double ld;
  11.  
  12. #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
  13. #define endl '\n'
  14. #define pb push_back
  15. #define conts continue
  16. #define all(a) a.begin(),a.end()
  17. #define rall(a) a.rbegin(), a.rend()
  18. #define yes cout << "YES" << endl
  19. #define no cout << "NO" << endl
  20. #define ff first
  21. #define ss second
  22. #define ceil2(x,y) ((x+y-1) / y)
  23. #define sz(a) a.size()
  24. #define setbits(x) __builtin_popcountll(x)
  25. #ifndef ONLINE_JUDGE
  26. #define debug(x) cout << #x <<" = "; print(x); cout << endl;
  27. #else
  28. #define debug(x)
  29. #endif
  30.  
  31. #define rep(i,n) for(int i = 0; i < n; ++i)
  32. #define rep1(i,n) for(int i = 1; i <= n; ++i)
  33.  
  34. bool iseven(ll n) {if ((n & 1) == 0) return true; return false;}
  35.  
  36. void print(ll t) {cout << t;}
  37. void print(int t) {cout << t;}
  38. void print(string t) {cout << t;}
  39. void print(char t) {cout << t;}
  40. void print(double t) {cout << t;}
  41. void print(ld t) {cout << t;}
  42.  
  43. template <class T, class V> void print(pair <T, V> p);
  44. template <class T> void print(vector <T> v);
  45. template <class T> void print(set <T> v);
  46. template <class T, class V> void print(map <T, V> v);
  47. template <class T> void print(multiset <T> v);
  48. template <class T, class V> void print(pair <T, V> p) {cout << "{"; print(p.ff); cout << ","; print(p.ss); cout << "}";}
  49. template <class T> void print(vector <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";}
  50. template <class T> void print(set <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";}
  51. template <class T> void print(multiset <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";}
  52. template <class T, class V> void print(map <T, V> v) {cout << "[ "; for (auto i : v) {print(i); cout << " ";} cout << "]";}
  53.  
  54. void usaco(string filename) {
  55.     freopen((filename + ".in").c_str(), "r", stdin);
  56.     freopen((filename + ".out").c_str(), "w", stdout);
  57. }
  58.  
  59. int MOD = 1e9 + 7;
  60. const int maxn = 1e5 + 5;
  61. const int inf1 = 1e9 + 5;
  62. const ll inf2 = 1e18 + 5;
  63.  
  64. template<typename T, int sp>
  65. struct segtree {
  66.     /*=======================================================*/
  67.  
  68.     struct data {
  69.         int a, b, c, d;
  70.     };
  71.  
  72.     data neutral = {1, 0, 0, 1};
  73.  
  74.     void merge(data &curr, data &left, data &right) {
  75.         /*
  76.         [a1,b1] * [a2,b2] = [a1a2 + b1c2, a1b2 + b1d2]
  77.         [c1,d1]   [c2,d2]   [c1a2 + d1c2, c1b2 + d1d2]
  78.         */
  79.  
  80.         auto [a1, b1, c1, d1] = left;
  81.         auto [a2, b2, c2, d2] = right;
  82.  
  83.         int a3, b3, c3, d3;
  84.  
  85.         a3 = a1 * a2 + b1 * c2;
  86.         b3 = a1 * b2 + b1 * d2;
  87.         c3 = c1 * a2 + d1 * c2;
  88.         d3 = c1 * b2 + d1 * d2;
  89.  
  90.         a3 %= MOD, b3 %= MOD, c3 %= MOD, d3 %= MOD;
  91.         curr = {a3, b3, c3, d3};
  92.     }
  93.  
  94.     void create(int x, int lx, int rx, T v) {
  95.         auto [a, b, c, d] = v;
  96.         tr[x] = {a, b, c, d};
  97.     }
  98.  
  99.     void modify(int x, int lx, int rx, T v) {
  100.  
  101.     }
  102.  
  103.     /*=======================================================*/
  104.  
  105.     int siz = 1;
  106.     vector<data> tr;
  107.  
  108.     segtree(int n) {
  109.         init(n);
  110.     }
  111.  
  112.     segtree() {
  113.  
  114.     };
  115.  
  116.     void init(int n) {
  117.         while (siz < n) siz *= 2;
  118.         tr.assign(2 * siz, neutral);
  119.     }
  120.  
  121.     void build(vector<T> &a, int n, int x, int lx, int rx) {
  122.         if (rx - lx == 1) {
  123.             if (lx >= sp and lx < n) {
  124.                 create(x, lx, rx, a[lx]);
  125.             }
  126.  
  127.             return;
  128.         }
  129.  
  130.         int mid = (lx + rx) / 2;
  131.  
  132.         build(a, n, 2 * x + 1, lx, mid);
  133.         build(a, n, 2 * x + 2, mid, rx);
  134.  
  135.         merge(tr[x], tr[2 * x + 1], tr[2 * x + 2]);
  136.     }
  137.  
  138.     void build(vector<T> &a, int n) {
  139.         build(a, n, 0, 0, siz);
  140.     }
  141.  
  142.     void pupd(int i, T v, int x, int lx, int rx) {
  143.         if (rx - lx == 1) {
  144.             modify(x, lx, rx, v);
  145.             return;
  146.         }
  147.  
  148.         int mid = (lx + rx) / 2;
  149.  
  150.         if (i < mid) {
  151.             pupd(i, v, 2 * x + 1, lx, mid);
  152.         }
  153.         else {
  154.             pupd(i, v, 2 * x + 2, mid, rx);
  155.         }
  156.  
  157.         merge(tr[x], tr[2 * x + 1], tr[2 * x + 2]);
  158.     }
  159.  
  160.     void pupd(int i, T v) {
  161.         pupd(i, v, 0, 0, siz);
  162.     }
  163.  
  164.     data query(int l, int r, int x, int lx, int rx) {
  165.         if (lx >= r or rx <= l) return neutral;
  166.         if (lx >= l and rx <= r) return tr[x];
  167.  
  168.         int mid = (lx + rx) / 2;
  169.  
  170.         data curr;
  171.         data left = query(l, r, 2 * x + 1, lx, mid);
  172.         data right = query(l, r, 2 * x + 2, mid, rx);
  173.  
  174.         merge(curr, left, right);
  175.         return curr;
  176.     }
  177.  
  178.     data query(int l, int r) {
  179.         return query(l, r + 1, 0, 0, siz);
  180.     }
  181. };
  182.  
  183. void solve(int test_case)
  184. {
  185.     cin >> MOD;
  186.     int n, m; cin >> n >> m;
  187.  
  188.     vector<array<int, 4>> a(n + 5);
  189.     rep1(i, n) {
  190.         rep(j, 4) cin >> a[i][j], a[i][j] %= MOD;
  191.     }
  192.  
  193.     segtree<array<int, 4>, 1> st(n + 5);
  194.     st.build(a, n + 1);
  195.  
  196.     while (m--) {
  197.         int l, r; cin >> l >> r;
  198.         auto ans = st.query(l, r);
  199.  
  200.         cout << ans.a << " " << ans.b << endl;
  201.         cout << ans.c << " " << ans.d << endl;
  202.         cout << endl;
  203.     }
  204. }
  205.  
  206. int main()
  207. {
  208.     fastio;
  209.  
  210.     int t = 1;
  211.     // cin >> t;
  212.     rep1(i, t) {
  213.         solve(i);
  214.     }
  215.  
  216.     return 0;
  217. }
Success #stdin #stdout 0.01s 5532KB
comments (?)
stdin
copy 
3 4 4
0 1
0 0

2 1
1 2

0 0
0 2

1 0
0 2

1 4
2 3
1 3
2 2
stdout
copy 
0 2
0 0

0 2
0 1

0 1
0 0

2 1
1 2
https://ideone.com/z7muax
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

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!