SHARE
TWEET

Untitled

a guest Feb 21st, 2019 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. #define N ((int)(1e5 + 5))
  5. #define MAX ((int)(1e7 + 5))
  6. struct info
  7. {
  8.     int h, i;
  9. } ar[N];
  10.  
  11. bool cmp1(info a, info b)
  12. {
  13.     return (a.h>b.h || (a.h==b.h && a.i>b.i));
  14. }
  15.  
  16. bool cmp2(info a, info b)
  17. {
  18.     return (a.h>b.h || (a.h==b.h && a.i<b.i));
  19. }
  20.  
  21. bool cmp(info a, info b)
  22. {
  23.     return a.i<b.i;
  24. }
  25.  
  26.  
  27. int sum[N*4], mn[N*4];
  28.  
  29. void init(int n, int b, int e)
  30. {
  31.     sum[n] = 0;
  32.     if(b==e)
  33.     {
  34.         mn[n] = ar[b].h;
  35.         return;
  36.     }
  37.  
  38.     int l, m;
  39.  
  40.     l = n<<1;
  41.     m = (b+e)>>1;
  42.     init(l,b,m);
  43.     init(l+1,m+1,e);
  44.     mn[n] = min(mn[l],mn[l+1]);
  45. }
  46.  
  47. int getid(int n, int b, int e, int i, int j, bool dir)
  48. {
  49.     if(sum[n]==0 || e<i || j<b || i>j)
  50.     {
  51.         if(dir==1) return N;
  52.         else return -1;
  53.     }
  54.  
  55.     if(b==e) return b;
  56.     int l,m;
  57.     l = n<<1;
  58.     m = (b+e)>>1;
  59.     if(i<=b && j>=e)
  60.     {
  61.         if(dir)
  62.         {
  63.             if(sum[l+1]>0) return getid(l+1,m+1,e,i,j,dir);
  64.             else return getid(l,b,m,i,j,dir);
  65.         }
  66.  
  67.         else
  68.         {
  69.             if(sum[l]>0) return getid(l,b,m,i,j,dir);
  70.             else return getid(l+1,m+1,e,i,j,dir);
  71.         }
  72.     }
  73.  
  74.     if(dir==0) return max(getid(l,b,m,i,j,dir),getid(l+1,m+1,e,i,j,dir));
  75.     return min(getid(l+1,m+1,e,i,j,dir),getid(l,b,m,i,j,dir));
  76.  
  77.  
  78. }
  79.  
  80. void update(int n, int b , int e, int i)
  81. {
  82.     if(i<b || i>e) return;
  83.     if(b==e){
  84.         sum[n]++;
  85.         return;
  86.     }
  87.  
  88.     int l , m;
  89.     l = n<<1;
  90.     m = (b+e)>>1;
  91.     update(l,b,m,i);
  92.     update(l+1,m+1,e,i);
  93.     sum[n] = sum[l]+sum[l+1];
  94. }
  95.  
  96. int getmin(int n, int b, int e, int i, int j)
  97. {
  98.     if(j<b || e<i || i>j) return MAX;
  99.     if(i<=b && j>=e) return mn[n];
  100.  
  101.     int l, m;
  102.     m = (b+e)>>1;
  103.     l = n<<1;
  104.     return min(getmin(l,b,m,i,j),getmin(l+1,m+1,e,i,j));
  105. }
  106.  
  107. int ans[N];
  108.  
  109. int main()
  110. {
  111.     int n;
  112.     while(!scanf("%d",&n)!=-1)
  113.     {
  114.         for(int i = 1; i<=n ; i++)
  115.         {
  116.             scanf("%d",&ar[i].h);
  117.             ar[i].i = i;
  118.             ans[i] = ar[i].h;
  119.         }
  120.         init(1,1,n);
  121.         sort(ar+1,ar+n+1,cmp1);
  122.  
  123.         for(int i = 1; i<=n; i++)
  124.         {
  125.             int j = ar[i].i;
  126.             int k = getid(1,1,n,1,j,0);
  127.             if(k<1) continue;
  128.             ans[j] = min(ans[j],getmin(1,1,n,k,j));
  129.             update(1,1,n,j);
  130.         }
  131.  
  132.         memset(sum,0,sizeof sum);
  133.  
  134.         sort(ar+1,ar+1+n, cmp2);
  135.  
  136.         for(int i = 1; i<=n; i++)
  137.         {
  138.  
  139.             int j = ar[i].i;
  140.             int k = getid(1,1,n,j,n,1);
  141.             if(k>n) continue;
  142.             ans[j] = max(ans[j],getmin(1,1,n,j,k));
  143.         }
  144.         sort(ar+1,ar+1+n,cmp);
  145.         for(int i = 1; i<=n; i++)
  146.         {
  147.             if(ar[i].h-ans[i]>=150000) printf("%d ",i);
  148.         }
  149.         printf("\n");
  150.     }
  151.     return 0;
  152. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top