fork download
copy 
  1. /**********************************************************************************************
  2. ->                      @author : a_e_kasem
  3. ***********************************************************************************************/
  4. //*------------------------------------------------------------------------------------------*//
  5. //                                  ﷽
  6. //                            { وَأَنْ لَيْسَ لِلْإِنْسَانِ إِلَّا مَا سَعَى }
  7. //
  8. //                     فَالجُهدُ يُثمِرُ إنْ تَضافَرَ صَفوُهُ، والعَزمُ يَرفعُ صَرحَ كُلِّ بُنيانِ
  9. //
  10. //                              وَما نَيلُ المَطالِبِ بِالتَمَنّي
  11. //                               وَلَكِن تُؤخَذُ الدُنيا غِلابا
  12. //                                     ***
  13. //                             وَما اِستَعصى عَلى قَومٍ مَنالٌ
  14. //                             إِذا الإِقدامُ كانَ لَهُم رِكابا
  15. //*------------------------------------------------------------------------------------------*//
  16. #include <bits/stdc++.h>
  17. using namespace std;
  18. #include <ext/pb_ds/assoc_container.hpp>
  19. #include <ext/pb_ds/tree_policy.hpp>
  20.  
  21. using namespace __gnu_pbds;
  22.  
  23. // Template definition for ordered_set
  24. template<typename T>
  25. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  26.  
  27.  
  28. #define int long long
  29. #define NO void(cout << "NO\n")
  30. #define YES void(cout << "YES\n")
  31. #define endl ("\n")
  32. const int oo = 1e18;
  33. const int N = 1e6+5;
  34.  
  35.  
  36. struct SparseTable {
  37.     int n, LOG;
  38.     vector<vector<pair<int, int>>> st;
  39.     vector<int> lg;
  40.  
  41.     pair<int, int> merge(const pair<int, int>& a, const pair<int, int>& b) {
  42.         if (a.first >= b.first) return a;
  43.         return b;
  44.     }
  45.  
  46.     SparseTable(const vector<int>& a) {
  47.         n = a.size();
  48.         LOG = 0;
  49.         while ((1 << LOG) <= n) LOG++;
  50.  
  51.         st.assign(LOG, vector<pair<int, int>>(n));
  52.         lg.assign(n + 1, 0);
  53.  
  54.         for (int i = 2; i <= n; i++)
  55.             lg[i] = lg[i / 2] + 1;
  56.  
  57.         for (int i = 0; i < n; i++)
  58.             st[0][i] = {a[i], i};
  59.  
  60.         for (int i = 1; i < LOG; i++) {
  61.             for (int j = 0; j + (1 << i) <= n; j++) {
  62.                 st[i][j] = merge(
  63.                     st[i - 1][j],
  64.                     st[i - 1][j + (1 << (i - 1))]
  65.                 );
  66.             }
  67.         }
  68.     }
  69.  
  70.     // query on [l, r] inclusive (0-based)
  71.     pair<int, int> query(int l, int r) {
  72.         int len = r - l + 1;
  73.         int i = lg[len];
  74.         return merge(
  75.             st[i][l],
  76.             st[i][r - (1 << i) + 1]
  77.         );
  78.     }
  79. };
  80.  
  81. void EL7L()
  82. {
  83.     int n, q; cin >> n >> q;
  84.     vector<int> a(n);
  85.     for (auto &it : a) cin >> it;
  86.     SparseTable st(a);
  87.  
  88.     vector<vector<int>> pref(n, vector<int>(2, 0)), suff(n, vector<int> (2, 0));
  89.     for (int i = n; i >= 1; i--) {
  90.         int l = 1, r = i - 1;
  91.         int ans = 0;
  92.         while (l <= r) {
  93.             int mid = (l+r)>>1;
  94.             if (st.query(mid, i - 1).first > a[i]) {
  95.                 ans = mid;
  96.                 l = mid + 1;
  97.             } else {
  98.                 r = mid - 1;
  99.             }
  100.         }
  101.         pref[i][0] = ans;
  102.     }
  103.     for (int i = 1; i <= n; i++) {
  104.         int l = i + 1, r = n, ans = n + 1;
  105.         while (l <= r) {
  106.             int mid = (l+r)>>1;
  107.             if (st.query(i + 1, mid).first > a[i]) {
  108.                 ans = mid;
  109.                 r = mid - 1;
  110.             } else {
  111.                 l = mid + 1;
  112.             }
  113.         }
  114.         suff[i][0] = ans;
  115.     }
  116.  
  117.  
  118.  
  119.     while (q--)
  120.     {
  121.         int l, r; cin >> l >> r;
  122.         l--, r--;
  123.  
  124.  
  125.  
  126.  
  127.     }
  128. }
  129.  
  130.  
  131.  
  132.  
  133. int32_t main()
  134. {
  135. #ifdef ONLINE_JUDGE
  136.     ios_base::sync_with_stdio(0);
  137.     cin.tie(0);
  138. #endif // ONLINE_JUDGE
  139.     // freopen("foot.in", "r", stdin);
  140.     int t = 1;
  141.     cin >> t;
  142.     while (t--)
  143.         EL7L();
  144.     return 0;
  145. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GkUSgS
language:
C++ (gcc 8.3)
created:
2 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!