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. #include <iostream>
  5. #include <cstdlib>
  6. #include <vector>
  7. #include <set>
  8. #include <deque>
  9. #include <utility>
  10. #include <cmath>
  11. #include <string>
  12. #include <cstring>
  13. #include <iomanip>
  14. #include <cctype>
  15. #include <algorithm>
  16. #include <numeric>
  17. #define Yellow_Flash              \
  18.     ios_base::sync_with_stdio(0); \
  19.     cin.tie(0);                   \
  20.     cout.tie(0)
  21. #define pi 3.14159265358979323
  22. #define el "\n"
  23. #define ll long long
  24. #define sp ' '
  25. #define MAX INT_MAX
  26. #define MIN INT_MIN
  27.  
  28. using namespace std;
  29. using namespace __gnu_pbds;
  30.  
  31. ll Sum(ll num)
  32. {
  33.     return num * (num + 1) / 2;
  34. }
  35. ll SumOdd(ll num)
  36. {
  37.     long long res = (num + 1) / 2;
  38.     long long finalRes = res * res;
  39.     return finalRes;
  40. }
  41. ll SumEven(ll num)
  42. {
  43.     long long res = (num * (num + 1));
  44.     return res;
  45. }
  46. bool Odd(ll num)
  47. {
  48.     if (num & 1)
  49.         return true;
  50.     else
  51.         return false;
  52. }
  53. bool Even(ll num)
  54. {
  55.     if (num & 1)
  56.         return false;
  57.     else
  58.         return true;
  59. }
  60. bool Palindrome_L(ll num)
  61. {
  62.     ll cpy = num, palin = 0;
  63.     while (num > 0)
  64.     {
  65.         palin += num % 10;
  66.         num /= 10;
  67.         if (num)
  68.             palin *= 10;
  69.     }
  70.     if (cpy == palin)
  71.         return true;
  72.     else
  73.         return false;
  74. }
  75. bool Palindrome_S(string s)
  76. {
  77.     string cpy = s;
  78.     reverse(s.begin(), s.end());
  79.     if (cpy == s)
  80.         return true;
  81.     else
  82.         return false;
  83. }
  84. string ToBinary(ll num)
  85. {
  86.     string bin;
  87.     while (num > 0)
  88.     {
  89.         if (num & 1)
  90.         {
  91.             bin += '1';
  92.             num /= 2;
  93.         }
  94.         else
  95.         {
  96.             bin += '0';
  97.             num /= 2;
  98.         }
  99.     }
  100.     reverse(bin.begin(), bin.end());
  101.     return bin;
  102. }
  103. bool Prime(ll num)
  104. {
  105.     if (num < 2)
  106.         return false;
  107.     else
  108.     {
  109.         for (ll i = 2; i * i <= num; ++i)
  110.         {
  111.             if (num % i == 0)
  112.                 return false;
  113.         }
  114.     }
  115.     return true;
  116. }
  117. ll SumLtoR_divX(ll l, ll r, ll x)
  118. {
  119.     ll sum = (Sum(r / x) * x) - (Sum((l - 1) / x) * x);
  120.     return sum;
  121. }
  122. ll Factorial(ll num)
  123. {
  124.     ll fac = 1;
  125.     for (ll i = 2; i <= num; ++i)
  126.     {
  127.         fac *= i;
  128.     }
  129.     return fac;
  130. }
  131. ll PR(ll n, ll r)
  132. {
  133.     ll mul = 1;
  134.     while (r--)
  135.     {
  136.         mul *= n;
  137.     }
  138.     return mul;
  139. }
  140. ll NPR(ll n, ll r)
  141. {
  142.     return Factorial(n) / Factorial(n - r);
  143. }
  144. ll NCR(ll n, ll r)
  145. {
  146.     return Factorial(n) / (Factorial(r) * Factorial(n - r));
  147. }
  148. ll CR(ll n, ll r)
  149. {
  150.     return Factorial(r + n - 1) / (Factorial(r) * Factorial(n - 1));
  151. }
  152. ll GCD(ll x,ll y){
  153.     while (y!=0)
  154.     {
  155.         ll s=x;
  156.         x=y;
  157.         y=s%x;
  158.     }
  159.     return x;
  160. }
  161. bool LongDiv(string num, ll x)
  162. {
  163.     ll rem = 0;
  164.     for (int i = 0; i < num.size(); ++i)
  165.     {
  166.         rem = (rem * 10 + (num[i] - '0')) % x;
  167.     }
  168.     if (rem == 0)
  169.         return true;
  170.     else
  171.         return false;
  172. }
  173. ll To_Decimal(string num)
  174. {
  175.     ll e = 0, N = 0;
  176.     for (ll i = num.size() - 1; i >= 0; --i)
  177.     {
  178.         if (num[i] == '0')
  179.             e++;
  180.         else
  181.         {
  182.             N += pow(2, e);
  183.             e++;
  184.         }
  185.     }
  186.     return N;
  187. }
  188. int BinarySearch(vector<int> arr, int target)
  189. {
  190.     int l = 0;
  191.     int r = arr.size() - 1;
  192.  
  193.     while (l <= r)
  194.     {
  195.         int mid = l + (r - l) / 2;
  196.  
  197.         if (arr[mid] == target)
  198.         {
  199.             return mid;
  200.         }
  201.         else if (arr[mid] < target)
  202.         {
  203.             l = mid + 1;
  204.         }
  205.         else
  206.         {
  207.             r = mid - 1;
  208.         }
  209.     }
  210.     return -1;
  211. }
  212. ll LCM(ll a, ll b)
  213. {
  214.     ll res = (a / GCD(a, b)) * b;
  215.     return res;
  216. }
  217. ll Fast_power(ll num, ll pow)
  218. {
  219.     ll res = 1;
  220.     while (pow > 0)
  221.     {
  222.         if (Odd(pow))
  223.             res *= num;
  224.         num *= num;
  225.         pow /= 2;
  226.     }
  227.     return res;
  228. }
  229. ll Modular_fast_power(ll num, ll pow, ll M)
  230. {
  231.     ll res = 1;
  232.     while (pow > 0)
  233.     {
  234.         if (Odd(pow))
  235.             res *= (num % M);
  236.         num = ((num % M) * (num % M)) % M;
  237.         pow /= 2;
  238.     }
  239.     return res;
  240. }
  241. string AddLargeNums(string num1, string num2)
  242. {
  243.     string res="";
  244.     ll n1=num1.size(), n2=num2.size();
  245.     ll n=max(n1,n2), carry=0;
  246.     for(int i=0; i<n; ++i)
  247.     {
  248.         ll d1, d2;
  249.         if(i<n1) d1=num1[n1-1-i]-'0';
  250.         else d1=0;
  251.         if(i<n2) d2=num2[n2-1-i]-'0';
  252.         else d2=0;
  253.         ll sum=d1+d2+carry;
  254.         carry=sum/10;
  255.         res.push_back(sum%10+'0');
  256.     }
  257.     if(carry){
  258.         res.push_back(carry+'0');
  259.     }
  260.     reverse(res.begin(),res.end());
  261.     return res;
  262. }
  263. string MultiplyLargeNums(string num1, int mul)
  264. {
  265.     string res="";
  266.     ll carry=0, n=num1.size();
  267.     for(int i=0; i<n; ++i)
  268.     {
  269.         ll d=num1[n-i-1]-'0';
  270.         int p=d*mul+carry;
  271.         carry=p/10;
  272.         res.push_back(p%10+'0');
  273.     }
  274.     while(carry){
  275.         res.push_back(carry%10+'0');
  276.         carry/=10;
  277.     }
  278.     reverse(res.begin(),res.end());
  279.     return res;
  280. }
  281.  
  282. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  283.  
  284. bool comp (pair<string,ll> & a, pair<string,ll> & b){
  285.     if(a.second==b.second) return a.first<b.first;
  286.     else return a.second>b.second;
  287. }
  288.  
  289.  
  290.  
  291. int main()
  292. {
  293. #ifndef ONLINE_JUDGE
  294.     freopen("input.txt", "r", stdin);
  295.     freopen("output.txt", "w", stdout);
  296. #endif
  297.     Yellow_Flash;
  298.     ll t;
  299.     cin >> t;
  300.     while(t--){
  301.         ll n;
  302.         cin >> n;
  303.         vector<ll> v(n), beg(n), end(n);
  304.         stack<ll> st;
  305.         map<ll,ll> ind; 
  306.         for (int i=0; i<n; ++i) {
  307.             cin >> v[i];
  308.             ind[v[i]]=i;
  309.         }
  310.         for(int i=n-1; i>=0; --i){
  311.             while(!st.empty() && st.top()>v[i]) st.pop();
  312.             if(st.empty()) end[i]=ind[v[i]];
  313.             else end[i]=ind[st.top()];
  314.             st.push(v[i]);
  315.         }
  316.         for(int i=0; i<n; ++i){
  317.             while(!st.empty() && st.top()>v[i]) st.pop();
  318.             if(st.empty()) beg[i]=ind[v[i]];
  319.             else beg[i]=ind[st.top()];
  320.             st.push(v[i]);
  321.         }
  322.         ll mx=MIN;
  323.         for(int i=0; i<n; ++i){
  324.             if (beg[i]==-1 && end[i]==-1){
  325.                 mx=max(n,mx);
  326.             }
  327.             else if (beg[i]==-1) {
  328.                 mx=max(mx,end[i]);
  329.             }
  330.             else if (end[i]==-1) {
  331.                 mx=max(mx,n-(beg[i]+1));
  332.             }
  333.             else {
  334.                 mx=max(mx,end[i]-(beg[i]+1));
  335.             }
  336.             cout << beg[i] << sp << end[i] << sp << mx << el;
  337.         }
  338.     }
  339.     return 0;
  340. }
  341.                 /* Fight not to be the Winner ,but to be the last one to lose */
  342.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/baoniu
language:
C++ (gcc 8.3)
created:
12 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!