fork download
copy 
  1. /*
  2.     author: kartik8800
  3. */
  4.  
  5. #include<bits/stdc++.h>
  6. #define ll long long
  7. #define pb push_back
  8. #define fr(a,b) for(int i = a; i < b; i++)
  9. #define rep(i,a,b) for(int i = a; i < b; i++)
  10. #define mod 1000000007
  11. #define inf (1LL<<60)
  12. #define all(x) (x).begin(), (x).end()
  13. #define prDouble(x) cout << fixed << setprecision(10) << x
  14. #define triplet pair<ll,pair<ll,ll>>
  15. #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
  16. using namespace std;
  17. #define left(i) (2*i + 1)
  18. #define right(i) (2*i + 2)
  19. #define parent(i) ((i-1)/2)
  20. #include <vector>
  21.  
  22. template<class T>
  23. class SegmentTree
  24. {
  25.     public:
  26.         //tree constructors.
  27.         SegmentTree(std::vector<T> data, T value, T (*combine)(T obj1, T obj2));
  28.         SegmentTree(T ar[], int n, T value, T (*combine)(T obj1, T obj2));
  29.  
  30.         //query the range l to r, 0 based array indexing.
  31.         T query(int l, int r);
  32.  
  33.         //update the element at index idx to val.
  34.         void update(int idx, T val);
  35.         ///TODO lazy propagation
  36.     private:
  37.         //represents the segment tree.
  38.         T *tree;
  39.  
  40.         //builds the segment tree.
  41.         void buildTree(std::vector<T> data);
  42.  
  43.         //size of the segment tree array.
  44.         int segTreeSize;
  45.  
  46.         //extra nodes must be added to array to make its size a power of 2
  47.         //this is the value to be filled for the those nodes.
  48.         T valueForExtraNodes;
  49.  
  50.         //specifies how to combine child node results to form parent node result.
  51.         T (*combine)(T obj1, T obj2);
  52.  
  53.         //used to calculate the size of array needed to store the tree.
  54.         int calculateSize(int n);
  55.  
  56.         //helps to solve a range query.
  57.         T queryHelper(int l,int r, int st, int ed, int node);
  58. };
  59.  
  60. template<class T> SegmentTree<T>::SegmentTree(std::vector<T> data,
  61.                                                 T value, T (*combine)(T obj1, T obj2))
  62. {
  63.    this->combine = combine;
  64.    valueForExtraNodes = value;
  65.    segTreeSize = calculateSize(data.size());
  66.    buildTree(data);
  67. }
  68.  
  69. template<class T> SegmentTree<T>::SegmentTree(T ar[], int n,
  70.                                             T value, T (*combine)(T obj1, T obj2))
  71. {
  72.    this->combine = combine;
  73.    valueForExtraNodes = value;
  74.    segTreeSize = calculateSize(n);
  75.  
  76.    std::vector<T> data;
  77.    for(int i = 0; i < n; i++)
  78.          data.push_back(ar[i]);
  79.  
  80.    buildTree(data);
  81. }
  82.  
  83.  
  84. template<class T> int SegmentTree<T>::calculateSize(int n)
  85. {
  86.     int pow2 = 1;
  87.     while( pow2 < n)
  88.     {
  89.         pow2 = pow2 << 1;
  90.     }
  91.     return 2*pow2 - 1;
  92. }
  93.  
  94. template<class T> T SegmentTree<T>::query(int l, int r)
  95. {
  96.     int st = 0, ed = segTreeSize/2;
  97.     return queryHelper(l, r, st, ed, 0);
  98. }
  99.  
  100. template<class T> T SegmentTree<T>::queryHelper(int l,int r, int st, int ed, int node)
  101. {
  102.     if( (r < st) || (l > ed) || (l > r) )
  103.         return valueForExtraNodes;
  104.     if(st >= l && ed <= r)
  105.         return tree[node];
  106.     T leftVal = queryHelper(l, r, st, (st + ed)/2, left(node));
  107.     T rightVal = queryHelper(l, r, (st+ed)/2 + 1, ed, right(node));
  108.     return combine(leftVal, rightVal);
  109. }
  110.  
  111. template<class T> void SegmentTree<T>::buildTree(std::vector<T> data)
  112. {
  113.    int n = data.size();
  114.    tree = new T[segTreeSize];
  115.    int extraNodes = (segTreeSize/2 + 1) - n;
  116.    for(int i = segTreeSize - 1; i >= 0; i--)
  117.    {
  118.        if(extraNodes>0)
  119.            {
  120.                tree[i] = valueForExtraNodes;
  121.                extraNodes--;
  122.            }
  123.        else if(n>0)
  124.            {
  125.                tree[i] = data[n-1];
  126.                n--;
  127.            }
  128.        else
  129.            tree[i] = combine(tree[left(i)], tree[right(i)]);
  130.    }
  131. }
  132.  
  133. template<class T> void SegmentTree<T>::update(int idx, T val)
  134. {
  135.     int segTreeIdx = (segTreeSize/2) + idx;
  136.     tree[segTreeIdx] = val;
  137.     while(parent(segTreeIdx) >= 0)
  138.     {
  139.         segTreeIdx = parent(segTreeIdx);
  140.         if(right(segTreeIdx) < segTreeSize)
  141.           tree[segTreeIdx] = combine(tree[left(segTreeIdx)], tree[right(segTreeIdx)]);
  142.         if(segTreeIdx == 0)
  143.             break;
  144.     }
  145. }
  146.  
  147. int large(int x, int y){return max(x,y);}
  148. SegmentTree < int > rangeMaxQueries(vector<int>(),0,large);
  149.  
  150. int RMQ(int L, int R)
  151. {
  152.     if(L>R)return 0;
  153.     return rangeMaxQueries.query(L,R);
  154. }
  155.  
  156. void whatsWithThisOPFormat(){
  157.     static int tno = 1;
  158.     cout << "Case #" <<tno++ <<": ";
  159. }
  160.  
  161. int solve(vector<int>& v, int strt, int k)
  162. {
  163.     if(k == 1)return strt;
  164.  
  165.     // binary search left region
  166.     int lo = 1, hi = strt - 1;
  167.     while(lo <= hi){
  168.         int mid = (lo+hi)/2;
  169.         int rightRoom = k + mid - 1;
  170.  
  171.         if(rightRoom < strt)
  172.             lo = mid + 1;
  173.  
  174.         else if(rightRoom > (int)v.size() - 1)
  175.             hi = mid -1;
  176.  
  177.         else{
  178.             bool reachRight1st = (RMQ(mid, strt - 1) > RMQ(strt, rightRoom - 1)) ? 1 : 0;
  179.             bool reachMid = (RMQ(mid, strt - 1) < RMQ(strt, rightRoom)) ? 1 : 0;
  180.             if(reachMid && reachRight1st)
  181.                 return mid;
  182.             else if(reachMid)
  183.                 hi = mid - 1;
  184.             else lo = mid + 1;
  185.         }
  186.     }
  187.  
  188.     // binary search right region
  189.     lo = strt+1, hi = (int)v.size() - 1;
  190.     while(lo <= hi){
  191.  
  192.         int mid = (lo+hi)/2;
  193.         int leftRoom = mid - k + 1;
  194.  
  195.         if(leftRoom > strt)
  196.             hi = mid - 1;
  197.         else if(leftRoom <= 0)
  198.             lo = mid+1;
  199.  
  200.         else{
  201.             bool reachLeft1st = (RMQ(leftRoom, strt - 1) < RMQ(strt, mid - 1)) ? 1 : 0;
  202.             bool reachMid = (RMQ(leftRoom - 1, strt - 1) > RMQ(strt, mid - 1)) ? 1 : 0;
  203.             if(reachMid && reachLeft1st)
  204.                 return mid;
  205.             else if(reachMid)
  206.                 lo = mid + 1;
  207.             else hi = mid - 1;
  208.         }
  209.     }
  210.     return -1;
  211. }
  212.  
  213. int main() {
  214.    fast_io;
  215.    ll t,n,m,x,i,j,k,q;
  216.    cin >> t;
  217.    //t = 1;
  218.    while(t--)
  219.    {
  220.         cin >> n >> q;
  221.         vector<int> difficulty(n+1);
  222.  
  223.         fr(1,n)
  224.             cin >> difficulty[i];
  225.         difficulty[0] = difficulty[n] = 1e9;
  226.  
  227.         rangeMaxQueries = SegmentTree<int>(difficulty,0,large);
  228.         vector<int> ans;
  229.         while(q--){
  230.             int strt, k;
  231.             cin >> strt >> k;
  232.             ans.push_back(solve(difficulty, strt, k));
  233.         }
  234.  
  235.         whatsWithThisOPFormat();
  236.         for(int x : ans)cout << x <<' ';
  237.         cout << '\n';
  238.    }
  239.    return 0;
  240. }
  241.  
Success #stdin #stdout 0s 4180KB
comments (?)
stdin
copy 
2
5 4
90 30 40 60
3 4
3 1
1 5
4 3
10 2
6 2 4 5 9 30 7 1 8
6 8
6 8
stdout
copy 
Case #1: 5 3 5 2 
Case #2: 8 8
https://ideone.com/1YaN4q
language:
C++14 (gcc 8.3)
created:
4 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!