fork download
copy 
  1. /*
  2. * Author: Geeza
  3. */
  4.  
  5. #include <bits/stdc++.h>
  6.  
  7. #define ld long double
  8. #define ll long long
  9. #define pb push_back
  10. #define fin(a, n) for(int i = a; i < n; i++)
  11. #define fjn(a, n) for(int j = a; j < n; j++)
  12. #define all(a) a.begin(),a.end()
  13. #define allr(a) a.rbegin(),a.rend()
  14. #define FAST ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
  15.  
  16. using namespace std;
  17.  
  18. const double PI = acos(-1);
  19. const int N = 2e3+10;
  20. const ll oo = 0x3f3f3f3f3f3f3f3f;
  21. const int MOD = 1000000007, inf = 1e6;
  22.  
  23. string di[] = {"D","L", "U", "R", "UL", "UR", "DL", "DR"};
  24. int dx[] = {+1, +0, +0, -1, -1, -1, +1, +1};
  25. int dy[] = {+0, -1, +1, +0, -1, +1, -1, +1};
  26. char dc[] = {'D', 'L', 'R', 'U'};
  27.  
  28. ll r;
  29.  
  30. ll mult(ll a, ll b) {
  31.     return ((a%r) * (b%r)) % r;
  32. }
  33.  
  34. void mul(ll a[2][2], ll b[2][2], ll res[2][2]) {
  35.     res[0][0] = (mult(a[0][0], b[0][0]) + mult(a[0][1], b[1][0])) % r;
  36.     res[0][1] = (mult(a[0][0], b[0][1]) + mult(a[0][1], b[1][1])) % r;
  37.     res[1][0] = (mult(a[1][0], b[0][0]) + mult(a[1][1], b[1][0])) % r;
  38.     res[1][1] = (mult(a[1][0], b[0][1]) + mult(a[1][1], b[1][1])) % r;
  39. }
  40.  
  41. ll id[2][2] = {{1,0},{0,1}};
  42.  
  43. struct node {
  44.     ll mat[2][2];
  45.  
  46.     node() {
  47.         for (int i = 0; i < 2; i++) {
  48.             for (int j = 0; j < 2; j++) {
  49.                 mat[i][j] = id[i][j];
  50.             }
  51.         }
  52.     }
  53.  
  54.     node(ll arr[2][2]) {
  55.         for (int i = 0; i < 2; i++) {
  56.             for (int j = 0; j < 2; j++) {
  57.                 mat[i][j] = arr[i][j];
  58.             }
  59.         }
  60.     }
  61.  
  62.     void change(ll arr[2][2]) {
  63.         for (int i = 0; i < 2; i++) {
  64.             for (int j = 0; j < 2; j++) {
  65.                 mat[i][j] = arr[i][j];
  66.             }
  67.         }
  68.     }
  69. };
  70.  
  71. struct segTree {
  72.     ll treeSize;
  73.     vector<node> tree;
  74.  
  75.     segTree(ll n) {
  76.         treeSize = 1;
  77.         while (treeSize < n) treeSize <<= 1;
  78.         tree.resize(2 * treeSize, node());
  79.     }
  80.  
  81.     node merge(node &l, node &r) {
  82.         node par;
  83.         mul(l.mat, r.mat, par.mat);
  84.         return par;
  85.     }
  86.  
  87.     void set(ll arr[2][2], ll idx, ll i, ll l, ll r) {
  88.         if (r - l == 1) {
  89.             tree[i].change(arr);
  90.             return;
  91.         }
  92.         ll mid = l + (r - l) / 2;
  93.         if (idx < mid) set(arr, idx, 2 * i + 1, l, mid);
  94.         else set(arr, idx, 2 * i + 2, mid, r);
  95.         tree[i] = merge(tree[2 * i + 1], tree[2 * i + 2]);
  96.     }
  97.  
  98.     void set(ll arr[2][2], ll idx) {
  99.         set(arr, idx, 0, 0, treeSize);
  100.     }
  101.  
  102.     node get(ll lx, ll rx, ll i, ll l, ll r) {
  103.         if (lx <= l && rx >= r) return tree[i];
  104.         if (rx <= l || lx >= r) return node(id);
  105.         ll mid = l + (r - l)/2;
  106.         node lf = get(lx, rx, 2*i+1, l, mid);
  107.         node ri = get(lx, rx, 2*i+2, mid, r);
  108.         return merge(lf, ri);
  109.     }
  110.  
  111.     void get(ll l, ll r, ll res[2][2]) {
  112.         node ans = get(l, r, 0, 0, treeSize);
  113.         memcpy(res, ans.mat, sizeof(ll)*4);
  114.     }
  115. };
  116.  
  117. void solve() {
  118.     ll n, m; cin >> r >> n >> m;
  119.     segTree st(n);
  120.     fin(0, n) {
  121.         ll v[2][2];
  122.         cin >> v[0][0] >> v[0][1] >> v[1][0] >> v[1][1];
  123.         st.set(v, i);
  124.     }
  125.  
  126.     while(m--) {
  127.         ll a, b; cin >> a >> b;
  128.         a--;
  129.         ll ans[2][2];
  130.         st.get(a, b, ans);
  131.         for(int i = 0; i < 2; i++){
  132.             for(int j = 0; j < 2; j++){
  133.                 cout << ans[i][j] << " ";
  134.             }
  135.             cout << "\n";
  136.         }
  137.         cout << "\n";
  138.     }
  139. }
  140.  
  141. int main() {
  142.     FAST;
  143. #ifndef ONLINE_JUDGE
  144.     freopen("input.txt","r",stdin);
  145.     freopen("output.txt","w",stdout);
  146. #endif
  147.     int tt = 1; //cin >> tt;
  148.     while(tt--){
  149.         solve();
  150.     }
  151.     return 0;
  152. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ZJjdyF
language:
C++ (gcc 8.3)
created:
5 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!