fork download
copy 
  1.     #include <bits/stdc++.h>
  2.     #include <chrono>
  3.     using namespace std;
  4.     using namespace chrono;
  5.     // "AJEET JAIN"----"JAI JINENDRA"  
  6.     /* "णमो अरिहंताणं",
  7.         "णमो सिद्धाणं",
  8.         "णमो आयरियाणं",
  9.         "णमो उवज्झायाणं",
  10.         "णमो लोए सव्वसाहूणं",
  11.         "",
  12.         "एसो पंच नमोक्कारो, सव्व पावप्पणासणो",
  13.         "मंगलाणं च सव्वेसिं, पडमं हवै मंगलं",   */
  14.  
  15.  
  16.     // Aliases to op
  17.     using ll = long long;
  18.     using ull = unsigned long long;
  19.     using ld = double;
  20.     using vll = vector<ll>;
  21.  
  22.  
  23.     // Constants
  24.     constexpr ll INF = 4e18;
  25.     constexpr ld EPS = 1e-9;
  26.     constexpr ll MOD = 1e9 + 7;
  27.  
  28.  
  29.  
  30.     // Macros
  31.     #define F first
  32.     #define S second
  33.     #define all(x) begin(x), end(x)
  34.     #define allr(x) rbegin(x), rend(x)
  35.     #define py cout<<"YES\n";
  36.     #define pn cout<<"NO\n";
  37.     #define forn(i,n) for(int i=0;i<n;i++)
  38.     #define for1(i,n) for(int i=1;i<=n;i++)
  39.  
  40.     // #define insert push_back
  41.     #define pb push_back
  42.     #define MP make_pair
  43.     #define endl '\n'
  44.  
  45.     /*
  46.       remove substring or subarray ---> try to think about sliding w
  47.     
  48.     */                  
  49.  
  50.      /*
  51.       
  52.      Golden Rule
  53.  
  54.      1) problem is easy
  55.      2) proofs is easy
  56.      3) implementation is easy
  57.      
  58.      /*
  59.          ROUGH --
  60.  
  61.            first we have to choose the optimal starting way
  62.               what can be optimal start?
  63.                -> where we can reach the max building of the top
  64.                1 5 5 2 6
  65.             -> 1 1 0 1
  66.  
  67.               1 2 2 4 3 5 6   if(arr[i - 1] <= arr[i] then 1 else 0)
  68.               1 1 1 0 1 1
  69.  
  70.               5 4 3 2 7 8 1 9
  71.               0 0 0 1 1 0 1    if 0 is coming before 1 then it is optimal to start with the first occrecne of 1 just after 0
  72.               0 0 0 1 2 2 3
  73.  
  74.               1 1 1 1 0 0 1    // 1 define increment and 0 decrement
  75.               1 2 3 4 4 4 5
  76.                
  77.         ->    
  78.                  
  79.      */
  80.  
  81.     void AJNJ(){
  82.  
  83.         ll n;
  84.         cin >> n;
  85.         vector<ll> h(n);
  86.         forn(i , n){
  87.               cin >> h[i];
  88.         }
  89.         vector<ll> bin;
  90.         for(int i = 1 ; i < n ; i++){
  91.             if(h[i - 1] <= h[i]){
  92.                  bin.push_back(1);
  93.             }
  94.             else{
  95.                 bin.push_back(0);
  96.             }
  97.         }
  98.         vector <ll> pre(bin.size() , 0);
  99.         pre[0] = bin[0];
  100.         for(int i = 1 ; i < bin.size() ; i++){
  101.              pre[i] = pre[i - 1] + bin[i];
  102.         }
  103.         vector<ll> ans;
  104.         ll cnt = 0;
  105.         for(int i = 1 ; i < pre.size() ; i++){
  106.               if(pre[i - 1] == pre[i] && pre[i] > 0){
  107.                    ans.push_back(i + 1);
  108.               }
  109.               if(pre[i - 1] == pre[i] && pre[i] == 1){
  110.                      ++cnt;
  111.               }
  112.               else{
  113.                  ans.push_back(cnt + 1);
  114.                  cnt = 0;
  115.               }
  116.         }
  117.         if(cnt > 0){
  118.             ans.push_back(cnt + 1);
  119.         }
  120.         sort(allr(ans));
  121.  
  122.         cout << ans[0] << endl;
  123.  
  124.  
  125.     }
  126.  
  127.  
  128.     int main(){
  129.         ios::sync_with_stdio(0);
  130.         cin.tie(0);
  131.         cout.tie(0);
  132.         int T = 1;
  133.         cin>>T;
  134.         auto start1 = high_resolution_clock::now();
  135.         while(T--){
  136.             AJNJ();
  137.         }
  138.         auto stop1 = high_resolution_clock::now();
  139.         auto duration = duration_cast<microseconds>(stop1 - start1);
  140.         cerr << "Time: " << duration . count() / 1000 << " ms" << endl;
  141.  
  142.         return 0;
  143.     }
Success #stdin #stdout #stderr 0.19s 169068KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
stderr
copy 
Time: 191 ms
https://ideone.com/vqtM7i
language:
C++14 (clang 8.0)
created:
19 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!