fork download
copy 
  1. #include <algorithm>
  2. using namespace std;
  3.  
  4. #define MAXN 100005
  5. #define TS 262144
  6.  
  7. static int N,R,A[MAXN],EP[MAXN];
  8. static int sumtree[TS],erased[TS],maxtree[TS],ST=TS/2-1;
  9.  
  10. static struct NODE{
  11.     NODE(){}
  12.     NODE(int mx,int mn): max_val(mx), min_pos(mn){ }
  13.     int max_val,min_pos;
  14.     bool operator < (const NODE &ot)const{
  15.         return max_val!=ot.max_val?max_val<ot.max_val:min_pos>ot.min_pos;
  16.     }
  17. } tree[TS],ans(0,1);
  18.  
  19. int get_real_pos(int n,int l,int r,int p)
  20. {
  21.     int m=(l+r)>>1;
  22.     if (l == r) return m;
  23.     if (p <= sumtree[n+n]) return get_real_pos(n+n,l,m,p);
  24.     return get_real_pos(n+n+1,m+1,r,p-sumtree[n+n]);
  25. }
  26.  
  27. void erase(int n,int l,int r,int s,int e)
  28. {
  29.     if (r < s || l > e) return;
  30.     if (s <= l && r <= e){
  31.         erased[n] = 1;
  32.         sumtree[n] = 0;
  33.         return;
  34.     }
  35.     int m=(l+r)>>1;
  36.     erase(n+n,l,m,s,e);
  37.     erase(n+n+1,m+1,r,s,e);
  38.     if (erased[n]) sumtree[n] = 0;
  39.     else sumtree[n] = sumtree[n+n]+sumtree[n+n+1];
  40. }
  41.  
  42. int get_max(int l,int r)
  43. {
  44.     int ret=0;
  45.     for (;l<=r;l>>=1,r>>=1){
  46.         if (l&1) ret = max(ret,maxtree[l++]);
  47.         if (!(r&1)) ret = max(ret,maxtree[r--]);
  48.     }
  49.     return ret;
  50. }
  51.  
  52. NODE get_max_node(int l,int r)
  53. {
  54.     NODE ret(-1e9,-1e9);
  55.     for (;l<=r;l>>=1,r>>=1){
  56.         if (l&1) ret = max(ret,tree[l++]);
  57.         if (!(r&1)) ret = max(ret,tree[r--]);
  58.     }
  59.     return ret;
  60. }
  61.  
  62. void set_node(int n,const NODE &val)
  63. {
  64.     for (;n;n>>=1) tree[n] = max(tree[n],val);
  65. }
  66.  
  67. int GetBestPosition(int n, int C, int r, int *order, int *S, int *E)
  68. {
  69.     int i,s,e;
  70.     N = n, R = ++r;
  71.     for (i=0;i<N-1;i++) A[i+1] = ++order[i];
  72.     for (i=1;i<=N;i++) sumtree[ST+i] = 1, EP[i] = i;
  73.     for (i=ST;i;i--) sumtree[i] = sumtree[i+i]+sumtree[i+i+1];
  74.     for (i=0;i<C;i++){
  75.         ++S[i]; ++E[i];
  76.         s = get_real_pos(1,1,TS>>1,S[i]);
  77.         e = get_real_pos(1,1,TS>>1,E[i]); e = EP[e];
  78.         S[i] = s; E[i] = e;
  79.         erase(1,1,TS>>1,s+1,e);
  80.         EP[s] = e;
  81.     }
  82.     for (i=1;i<N;i++) maxtree[ST+i] = A[i];
  83.     for (i=ST;i;i--) maxtree[i] = max(maxtree[i+i],maxtree[i+i+1]);
  84.     for (i=0;i<TS;i++) tree[i].max_val = -1e9;
  85.     for (i=0;i<C;i++){
  86.         if (get_max(ST+S[i],ST+E[i]-1) > R) continue;
  87.         NODE me(1,S[i]),mx;
  88.         mx = get_max_node(ST+S[i],ST+E[i]-1);
  89.         mx.max_val++;
  90.         if (me < mx) me = mx;
  91.         set_node(ST+S[i],me);
  92.         ans = max(ans,me);
  93.     }
  94.     return --ans.min_pos;
  95. }
  96.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/qCb8W4
language:
C++ (gcc 8.3)
created:
10 years 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!