fork download
copy 
  1. #include<cstring>
  2. #include<cstdlib>
  3. //#include<cstdio>
  4. #include<algorithm>
  5. using namespace std;
  6. struct Node
  7. {
  8.     pair<int,int> v;
  9.     int ansv;
  10.     int ansi;
  11.     int sz;
  12.     Node *l;
  13.     Node *r;
  14.     Node *p;
  15. };
  16. Node *root;
  17. void UpdateSize(Node *P)
  18. {
  19.     P->sz=1;
  20.     if(P->l) P->sz+=P->l->sz;
  21.     if(P->r) P->sz+=P->r->sz;
  22.  
  23. }
  24. void RightRotate(Node *P)
  25. {
  26.     Node *T=P->l;
  27.     Node *B=T->r;
  28.     Node *D=P->p;
  29.     if(D)
  30.     {
  31.         if(D->l==P) D->l=T;
  32.         else D->r=T;
  33.     }
  34.     if(B)
  35.         B->p=P;
  36.  
  37.     P->p=T;
  38.     P->l=B;
  39.     UpdateSize(P);
  40.  
  41.     T->r=P;
  42.     T->p=D;
  43.     UpdateSize(T);
  44. }
  45. void LeftRotate(Node *P)
  46. {
  47.     Node *T=P->r;
  48.     Node *B=T->l;
  49.     Node *D=P->p;
  50.     if(D)
  51.     {
  52.         if(D->l==P) D->l=T;
  53.         else D->r=T;
  54.     }
  55.     if(B)
  56.         B->p=P;
  57.  
  58.     P->p=T;
  59.     P->r=B;
  60.     UpdateSize(P);
  61.  
  62.     T->l=P;
  63.     T->p=D;
  64.     UpdateSize(T);
  65. }
  66. void Splay(Node *P)
  67. {
  68.     while(P->p)
  69.     {
  70.         Node* PP=P->p;
  71.         Node* PPP=PP->p;
  72.         if(!PPP)
  73.         {
  74.             if(PP->l==P) RightRotate(PP);
  75.             else LeftRotate(PP);
  76.             break;
  77.         }
  78.         if(PPP->l==PP)
  79.         {
  80.             if(PP->l==P)
  81.             {
  82.                 RightRotate(PPP);
  83.                 RightRotate(PP);
  84.             }
  85.             else
  86.             {
  87.                 LeftRotate(PP);
  88.                 RightRotate(PPP);
  89.             }
  90.         }
  91.         else
  92.         {
  93.             if(PP->l==P)
  94.             {
  95.                 RightRotate(PP);
  96.                 LeftRotate(PPP);
  97.             }
  98.             else
  99.             {
  100.                 LeftRotate(PPP);
  101.                 LeftRotate(PP);
  102.             }
  103.         }
  104.     }
  105.     root=P;
  106. }
  107. void Insert(pair<int, int> v,int ansv,int ansi)
  108. {
  109.     Node *T=root;
  110.     if(!T)
  111.     {
  112.         root=(Node*) malloc(sizeof(Node));
  113.         root->l=NULL;
  114.         root->r=NULL;
  115.         root->p=NULL;
  116.         root->v=v;
  117.         root->sz=1;
  118.         root->ansv=ansv;
  119.         root->ansi=ansi;
  120.         return;
  121.     }
  122.     while(T)
  123.     {
  124.         if(v < (T->v) )
  125.         {
  126.             if(T->l)
  127.             {
  128.                 T=T->l;
  129.                 continue;
  130.             }
  131.             else
  132.             {
  133.                 T->l=(Node *)malloc(sizeof(Node));
  134.                 T->l->l=NULL;
  135.                 T->l->r=NULL;
  136.                 T->l->p=T;
  137.                 T->l->v=v;
  138.                 T->l->ansv=ansv;
  139.                 T->l->ansi=ansi;
  140.                 T->l->sz=1;
  141.                 T=T->l;
  142.                 break;
  143.             }
  144.         }
  145.         else
  146.         {
  147.             if(T->r)
  148.             {
  149.                 T=T->r;
  150.                 continue;
  151.             }
  152.             else
  153.             {
  154.                 T->r=(Node *)malloc(sizeof(Node));
  155.                 T->r->l=NULL;
  156.                 T->r->r=NULL;
  157.                 T->r->p=T;
  158.                 T->r->v=v;
  159.                 T->r->ansv=ansv;
  160.                 T->r->ansi=ansi;
  161.                 T->r->sz=1;
  162.                 T=T->r;
  163.                 break;
  164.             }
  165.         }
  166.     }
  167.     Node* tosplay=T;
  168.     while(T)
  169.     {
  170.         UpdateSize(T);
  171.         T=T->p;
  172.     }
  173.     Splay(tosplay);
  174. }
  175.  
  176. Node* Find(pair<int,int> v)
  177. {
  178.     Node *T=root;
  179.     while(T)
  180.     {
  181.         if(v==(T->v))
  182.         {
  183.             Splay(T);
  184.             return T;
  185.         }
  186.         if(v< (T->v))
  187.         {
  188.             if(T->l)
  189.             {
  190.                 T=T->l;
  191.             }
  192.             else
  193.             {
  194.                 Splay(T);
  195.                 return NULL;
  196.             }
  197.         }
  198.         else
  199.         {
  200.             if(T->r)
  201.             {
  202.                 T=T->r;
  203.             }
  204.             else
  205.             {
  206.                 Splay(T);
  207.                 return NULL;
  208.             }
  209.         }
  210.     }
  211.     return NULL;
  212. }
  213.  
  214. void Erase(Node *T)
  215. {
  216.     Splay(T);
  217.  
  218.     if(T->l)
  219.     {
  220.         root=T->l;
  221.         Node *x=root;
  222.         while(x->r) x=x->r;
  223.         x->r=T->r;
  224.         if(T->r) T->r->p=x;
  225.         while(x->p)
  226.         {
  227.             UpdateSize(x);
  228.             x=x->p;
  229.         }
  230.     }
  231.     else
  232.         root=T->r;
  233.     free(T);
  234.     if(root)root->p=NULL;
  235. }
  236.  
  237. Node* findKth(Node *T,int K)
  238. {
  239.     int sz=0;
  240.     if(T->l) sz=T->l->sz;
  241.     if(sz==K) return T;
  242.     if(sz>K)
  243.         return findKth(T->l,K);
  244.     else
  245.         return findKth(T->r,K-sz-1);
  246. }
  247. Node* findKth(int K)
  248. {
  249.     Node* Kth=findKth(root,K);
  250.     Splay(Kth);
  251.     return Kth;
  252. }
  253. int R;
  254. const int MAXN=131072;
  255. int idx[MAXN*2];
  256. int getmax(int l,int r)
  257. {
  258.     l+=MAXN;
  259.     r+=MAXN;
  260.     int ans=0;
  261.     while(l<=r)
  262.     {
  263.         if(l%2==1)
  264.             ans=max(ans,idx[l++]);
  265.         if(r%2==0)
  266.             ans=max(ans,idx[r--]);
  267.         l/=2;
  268.         r/=2;
  269.     }
  270.     return ans;
  271. }
  272. void Query(int A,int B) //from Ath Node to Bth Node (0-based)
  273. {
  274.     int findcount=B-A+1;
  275.     Node *Ath=findKth(A);
  276.     Node *Bth=findKth(B);
  277.     //printf("%d %d %d %d\n",A,B,(Ath->v).first,(Bth->v).first);
  278.     int ansv=-1;
  279.     int ansi=-1;
  280.     pair<int,int> v=make_pair((Ath->v).first,(Bth->v).second);
  281.     //printf("%d\n",root->sz);
  282.     for(int i=0;i<findcount;i++)
  283.     {
  284.     //  printf("%d %d\n",root->sz,A);
  285.         Node *Ath=findKth(A);
  286.         if(ansv < (Ath->ansv))
  287.         {
  288.             ansv=Ath->ansv;
  289.             ansi=Ath->ansi;
  290.         }
  291.         //printf("%d\n",root->sz);
  292.         Erase(Ath);
  293.     }
  294.     //puts("ok");
  295.     int ans=getmax(v.first,v.second-1);
  296.  
  297.     if(ans<R) ansv++;
  298.     Insert(v,ansv,ansi);
  299. }
  300.  
  301.  
  302. int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
  303. {
  304.     ::R=R;
  305.     for(int i=0;i<N;i++)
  306.         Insert(make_pair(i,i),0,i);
  307.     for(int i=0;i<N-1;i++)
  308.         idx[MAXN+i]=K[i];
  309.     for(int i=MAXN-1;i>=1;i--)
  310.         idx[i]=max(idx[2*i],idx[2*i+1]);
  311.     for(int i=0;i<C;i++)
  312.         Query(S[i],E[i]);
  313.     return root->ansi;  
  314. }
  315. int main(){}
Success #stdin #stdout 0s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/l4eTox
language:
C++14 (gcc 8.3)
created:
3 days 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!