fork download 
  1. // █▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀█
  2. // █░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█
  3. // █░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█
  4. // █░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▄▄█▀███▀▀▀▀▀██▀▀▀▀▄▄▄▄░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█
  5. // █░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄█▀▀░░▄▄██▀▀░░░▄█▀░░░░░░░▄█▀█▄▄░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█
  6. // █░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▄█▀▀░░░▄▄█▀█▀░░░░▄█░░░░░░░░░░░▀█░▀███▄▄░░░░░░░░░░░░░░░░░░░░░░░░░░█
  7. // █░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▄█▀░▄▄░▄█▀░░▄▀░░░░▄█░░░░░░░░░░░░░▀█░░█▄░▀█▄░░░░░░░░░░░░░░░░░░░░░░░░█
  8. // █░░░░░░░░░░░░░▄▄▄▄▄▄▄░░░░░░░░░░█▀▄█▀▀░█▀░░▄█▀░░░░█▀░░░░░░░░░░░░░░░█░░░█░░░░▀█░░░░░░░░░░░░░░░░░░░░░░█
  9. // █░░░░░░░░░░░░▀█▄▄▄▄▄█▀█▄░░░░░▄▀▄█▀░░░█░░░▄█░░░░░░█░░░░░░░░░░░░░░░░█░░░█░░░░░░█▄░░░░░░░░░░░░░░░░░░░░█
  10. // █░░░░░░░░░░░▄▄▀▀░░░░▀▀░▀█░░▄███▀░░░░░█░░░█░░░░░░░█░░░░░░░░▄░░░░░░░█░░░█░░░░░█░▀█▄░░░░░░░░░░░░░░░░░░█
  11. // █░░░░░░░░░▄█▀▄█▀░░▄█░░░░▀█▄▀▄█░░▄░░░░▀░░░░░░░░░░▄█░░░░░░░░█░░░░░░░█░░░█░░░░░█░░░█▄░░░░░░░░░░░░░░░░░█
  12. // █░░░░░░░░██▄██▀░░█▀░░▄▄▄▀▄██▀░░░█░░▄░░░░░░░░░░░░█▀░░░░░░░█▀░░░░░░██░░░█░░░░░█░░░░█▀▄░░░░░░░░░░░░░░░█
  13. // █░░░░░░░░▀░░█▀░▄██▄▄█▀░░▄██░░░░░█░░█░░░░░▄░░░░░░▀█░░░░░░░█░░░░░░▄█░░░░█░░░░░█░░░░░░▀█▄░░░░░░░░░░░░░█
  14. // █░░░░░░░░░░░█▄█▀░█▀░░░░▄█▀░░░░░░█░░█░░░░░█░░░░░░░█░░░░░░░█░░░░░▄█░░░░▄█░░░░░█░░░░░░░░▀▄▄▄█▀▀█▄░░░░░█
  15. // █░░░░░░░░░░░▀▄▄██▀▄▄▄▀▀▀█░░░░░░░█░░█░░░░░█░▄▄▄▄▄▄▀▀▀▀▀▀▀▀█▄▄▄▄▄█▄▄░░░█░░░░░░█░░░▄░░░░░█░░▄▄▄░█░░░░░█
  16. // █░░░░░░░░░░▄█▀▄█░▀█░░░░█▀░░░░░░░█░░█░█░░░███▄█▀██████▀▀▀▀▀░░░░░░░▀▀█▄█░░░░░▄█░░░█░░░░░█░░░▀████░░░░█
  17. // █░░░░░░░░░█▀░█▀░░░█░░░░█░░░░░░░░█░░█░█▄░█▀░░░░░▀███▄▀▀░░░░░░░░░▀▀▀█▄██▄▄▄░░█░░░░█░░░░░█░░░░░▀▀█▄░░░█
  18. // █░░░░░░░░▄█▄░░░▄▄█░░░░░█░░░░░░░░█░░█▀▀▀▀░░░░░░░██▄██░░░░░░░░░░░░█▀███▀▀▄█▀▀▀█▄▄░█░░░░░▀█░░██▄░░█▄░░█
  19. // █░░░░░░░█▀▄██▀██░░░░░░░█░░░░░░░░█▄░▀█░░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄███░░░▀█▄░░░▀▀█░░░█░░█░░▀█▀▀█▄█░░█
  20. // █░░░░░░░█░▀░░▄█░░░░░░░░█░░░░░░░░░█▄░▀█▄░░░▄▄▄▄▄▄▄▄▄▄░░░░░█▀░░░░░▀▀▀▀░░░░░░▀█░░░▄█░░▄▀░░█░▄▄█░░░▀▀░░█
  21. // █░░░░░░▄▀░░▄█▀░░░░░░░█▀█░░░░░▄░░░░█▄░░▀█▀▀▀░░░░░░░░░░░░░░░░░░░░▀█▄▄▄░░░░░░░░█▄░█░░▄█░░░██▀░░░░░░░░░█
  22. // █░░░░░██░▄█▀█░░░░░░░░█░▀▄░░░░░█░░░▀██▄▄▀█▄░░░░░░░░░░░░░▀▀░░░░░░░░░░▀▀█▄▄░░░░░██▀░▄█░░░███░░░░░░░░░░█
  23. // █░░░░▄█▀█▀░▄▀░░░░░░░░█░░█░░░░░░█▄░░▀▄░░▀▀██░░░░░░░▄▄▄▄▄▄▄▄▄░░░░░░░░░░░░▀▀▄▄▄▄█▄▄▀▀░░░░█░▀▄░░░░░░░░░█
  24. // █░░░░█░░░▄█▀░░░░░░░░░█▄░█▄░░░░░░▀█▄░▀█░░░░░▄▀▀▄░█▀▀░░░░░░░▀▀▀▀█▄░░░░░░░░░░░░█▀█░░░░░░░█░░█░░░░░░░░░█
  25. // █░░░░▀█░▄▀█░░░░░░░░░░░▀█▄██░░░░░░░░████▄░░█▀░░░▀░░░░░░░░░░░░░░░▀▀▄░░░░░░░░░░░░█░░░░░░█▀░░█▄░░░░░░░░█
  26. // █░░░░░█▄▀░█░░░░░░░░░░░░█░░░░░░█▀█▄░█▄░░▀▀░█░░░░░░░░░░░░░░░░░░░░░░█░░░░░░░░░░░░██▀█░░░▀▄░░░█░░░░░░░░█
  27. // █░░░░█▀░░░█▄▄░░░░░░░░░░█░░░██▄█░░▀█▄▀▄░░░░█▄░░░░░░░░░░░░░░░░░░░░░█░░░░░░░░░▄▄▀░▄█▀▀▀█░▀█▄░█░░░░░░░░█
  28. // █░░░░▀▄▄▄▄█▄▀█░░░░░░▄▄▄██▄▄█▄██▄░░██▄██░░░░█░░░░░░░░░░░░░░░░░░░░░█░░░░░░░░░█░░▄▀░░█▀█░░░░░█░░░░░░░░█
  29. // █░░░░░▀█▀░░░▄█▄█▀▀▀▀▀░░░░░░░█░██░░█░█▄▄▀▀▀▀▀▀▀▀▄▄▄▄▄▄░░░░░░░░░░░█▀░░░██▄░░█▀▄█░░▄█░░█░░░▄▄█░░░░░░░░█
  30. // █░░░░░░█▄░▄█▀░░░░░░░░░░░░░░░░█░█▄░█░█░▀█░░░░░░░░░░░░█▀▀▀▀▀▀▄▄▄▄██░░░█▀░█░█▀█▀░▄▄▀░▄█▀░░▀▀░█░░░░░░░░█
  31. // █░░░░░░░█▀▀░░░░░░░░░░░░░░░░░░█▄░█░█░█░░█░░░░░░░░░░░░█░░░░▄▄▄░░█░▀▀▀▀█░░██▀░░▄█▀░▄█▀░▀█░░░░█░░░░░░░░█
  32. // █░░░░░░█░░░░░░▄▄████████▄░░░░░█░░░█▄█░░█░░░░░░░░░░░░█░░░░███░░█░░░░░█░▄█▀░░░░░▄██▄░░░▀▀░░█░░░░░░░░░█
  33. // █░░░░░░█░░░░░█████████████▄░░░▀█░░░░▀░░▀▄░░░░░░░░░░░█░░░░░░░░░█░░░░░█▄▀░░░░▄░░█░░░▀█▄▄█▀▀░░░░░░░░░░█
  34. // █░░░░░░█▄░░░░▀███████▀▀▀▀▀█▄░░░▀▄░░░░░░░█░░░░░░░░░░░█░░░░░░░░░█░░░░█▀▀░░▄█▀░░█░░░░░██░░░░░░░░░░░░░░█
  35. // █░░░░░░░█░░░░░░███▀░░░░░░░░▀▄░░░▀█░░░░░░█░░░░░░░░░░░█░░░░░░░░░█░░░█▀░░░█▀░░░█▀░░░░▄█░░░░░░░░░░░░░░░█
  36. // █░░░░░░░▀▄░░░░░██░░░░░░░░░░░░▀░░░█░░░░░░▀█░░▄▄░░░░░░█░░░░░░░░▄█░░░█░░▄█░░░░░█░░░░░█░░░░░░░░░░░░░░░░█
  37. // █░░░░░░░░▀█░░▄█▀░░░░░░░░░░░░░░░░▄█░░░░░░░▀█░▀▀▀▀▀█▄▄█▄▄▄▄▄▄▄▄█▄▄▄█▀░░█░░░░░▄█░░░░░█░░░░░░░░░░░░░░░░█
  38. // █░░░░░░░░░█░▄▀░░░░░░░░░░░░░░░▄█▀▀▀█▄░░░░░░▀█░░░░░░▀▀██████████████░░█▀░░░░░█░░░░░█▀░░░░░░░░░░░░░░░░█
  39. // █░░░░░░░░░██▀░░░░░░░░░░░░░░▄██░░░░░█▄░░░░░░█░░░░░░░░█░░░░░▀▀▀▀▀█▀█░░█░░░░░░█░░░░░█░░░░░░░░░░░░░░░░░█
  40. // █░░░░░░░░░██▀░░░░░░░░░░░░░░██░░░░░░░█▄░░░░░█░░░░░░░░█░░░░░░░░░░█░▀█▄█░░░░░░███▄░░▀▄░░░░░░░░░░░░░░░░█
  41. // █░░░░░░░░░██▄▄░░░░░░░░░░░░▄██░░░░░░░░▀█▄░▄█▀░░░░░░░░█░░░░░░░░░▄█░░█▄░░░░░░░██░▀█▄░▀█░░░░░░░░░░░░░░░█
  42. // █░░░░░░░▄██▀░▀█▄░░░░░░░░░░██▀░░░░░░░░░░▀▀█░░░░░░░░░▄▀░░░░░░░░▄█░░░██▄░░░░░▄██░░░█▄░▀█░░░░░░░░░░░░░░█
  43. // █░░░░░░░██▀░░░░▀▀▄▄░░░░░░██▀█▄░░░░░░░░░░░▀▀▄▄▄▄▄▄▄▄█▄▄▄▄▄▄▄░░█░░░▄▀░█░░░░░▀░█░░░░▀▄░▀█░░░░░░░░░░░░░█
  44. // █░░░░░░██▀░░░░░░░░▀█▄░░▄██▀░░░▀▄░░░░░░░░░░░░▀██████████████████▄█▀░░▀█░░░░░░█░░░░░█▄░▀▄░░░░░░░░░░░░█
  45. // █░░░░░░██░░░░░░░░░░░▀█▄██▀░░░░░░█▄░░░░░░░░░░░▀███████████████████░░░░▀█░░░░█▀░░░░░░█░░█░░░░░░░░░░░░█
  46. // █░░░░░██░░░░░░░░░░░░░░██▀░░░░░░░░▀█▄░░░░░░░░░░▀█████████████████▀░░░░░▀█░░▄█░░░░░░░█▄░░█░░░░░░░░░░░█
  47. // █░░░░▄█░░░░░░░░░░░░░▄██▀░░░░░░░░░░░▀█▄░░░░░░░░░▀████████████████░░░░░░░▀▄█▀░░░░░░░█▀█░░▀▄░░░░░░░░░░█
  48. // █░░░░█░░░░░░░░░░░░▄▄██▀░░░░░░░░░░░░░░█▄░░░░░░░░░░██▀▀▀▀▀▀██▀▀▀█▀░░░░░░░░█▀░░░░░░░▄█░█▄░░▀█▄░░░░░░░░█
  49. // █░░░░█░░░░░░░░░░░███▀░░░░░░░░░░░░░░░░░█▄░░░░░░░░░░█▄░░░░░█░░░░█░░░░░░░▄█▀░░░░░░░▄█░░░█░░░░▀▄░░░░░░░█
  50. // █▄▄▄▄█▄▄▄▄▄▄▄▄▄▄██▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄█▄▄▄▄▄█▄▄▄▄█▄▄▄▄▄▄▄█▄▄▄▄▄▄▄▄▄█▄▄▄▄█▄▄▄▄▄██▄▄▄▄▄▄█
  51. #include<bits/stdc++.h> 
  52. using namespace std;
  53. int n,k1,k2;
  54. int a[1000001];
  55. int nxtr[1000001][20];
  56. int nxtl[1000001][20];
  57. vector<int>ad[1000001],er[1000001];
  58. set<int>s;
  59. set<int>::iterator it;
  60. void process(){
  61.     int ans=-1;
  62.     for(int i=1;i<=n;i++){
  63.         int u=i;
  64.         for(int j=0;j<20;j++){
  65.             if(((k2-1)>>j)&1)u=nxtl[u][j];
  66.         }
  67.         if(u){
  68.             ad[nxtl[u][0]+1].push_back(i);
  69.             er[u+1].push_back(i);
  70.         }
  71.     }
  72.     for(int i=1;i<=n;i++){
  73.         for(int j:ad[i])s.insert(j);
  74.         for(int j:er[i])s.erase(j);
  75.         int u=i,v;
  76.         for(int j=0;j<20;j++){
  77.             if(((k1-1)>>j)&1)u=nxtr[u][j];
  78.         }
  79.         if(u==0)continue;
  80.         v=nxtr[u][0];
  81.         if(v==0)v=n;
  82.         else v--;
  83.         it=s.upper_bound(v);
  84.         if(it!=s.begin()){
  85.             it--;
  86.             if(*it>=u)ans=max(ans,*it-i+1);
  87.         }
  88.     }
  89.     cout<<ans;
  90. }   
  91. stack<int>upnxt;
  92. void init(){
  93.     cin>>n>>k1>>k2;
  94.     for(int i=1;i<=n;i++){
  95.         cin>>a[i];
  96.         while(upnxt.size()&&a[upnxt.top()]<=a[i])upnxt.pop();
  97.         if(upnxt.size())nxtl[i][0]=upnxt.top();
  98.         else nxtl[i][0]=0;
  99.         upnxt.push(i);
  100.     }
  101.     while(upnxt.size())upnxt.pop();
  102.     for(int i=n;i;i--){
  103.         while(upnxt.size()&&a[upnxt.top()]<=a[i])upnxt.pop();
  104.         if(upnxt.size())nxtr[i][0]=upnxt.top();
  105.         else nxtr[i][0]=0;
  106.         upnxt.push(i);
  107.     }
  108.     for(int j=1;j<20;j++){
  109.         for(int i=1;i<=n;i++){
  110.             nxtl[i][j]=nxtl[nxtl[i][j-1]][j-1];
  111.             nxtr[i][j]=nxtr[nxtr[i][j-1]][j-1];
  112.         }
  113.     }
  114. }   
  115. int main(){
  116.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  117.     #define NAME "nazunasdish"
  118.     if(fopen(NAME".inp","r")){
  119.         freopen(NAME".inp","r",stdin);
  120.         freopen(NAME".out","w",stdout);
  121.     }
  122.     clock_t beg=clock();
  123.     init();
  124.     process();
  125.     cerr<<double(clock()-beg)/CLOCKS_PER_SEC;
  126. }
  127.  
Success #stdin #stdout 0.02s 52144KB
comments (?)
stdin 
Standard input is empty
stdout 
-1
https://ideone.com/H1mJmB
language:
C++14 (gcc 8.3)
created:
1 day 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!