이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
struct Node
{
pair<int,int> v;
int ansv;
int ansi;
int sz;
Node *l;
Node *r;
Node *p;
};
Node *root;
void UpdateSize(Node *P)
{
P->sz=1;
if(P->l) P->sz+=P->l->sz;
if(P->r) P->sz+=P->r->sz;
}
void RightRotate(Node *P)
{
Node *T=P->l;
Node *B=T->r;
Node *D=P->p;
if(D)
{
if(D->l==P) D->l=T;
else D->r=T;
}
if(B)
B->p=P;
P->p=T;
P->l=B;
UpdateSize(P);
T->r=P;
T->p=D;
UpdateSize(T);
}
void LeftRotate(Node *P)
{
Node *T=P->r;
Node *B=T->l;
Node *D=P->p;
if(D)
{
if(D->l==P) D->l=T;
else D->r=T;
}
if(B)
B->p=P;
P->p=T;
P->r=B;
UpdateSize(P);
T->l=P;
T->p=D;
UpdateSize(T);
}
void Splay(Node *P)
{
while(P->p)
{
Node* PP=P->p;
Node* PPP=PP->p;
if(!PPP)
{
if(PP->l==P) RightRotate(PP);
else LeftRotate(PP);
break;
}
if(PPP->l==PP)
{
if(PP->l==P)
{
RightRotate(PPP);
RightRotate(PP);
}
else
{
LeftRotate(PP);
RightRotate(PPP);
}
}
else
{
if(PP->l==P)
{
RightRotate(PP);
LeftRotate(PPP);
}
else
{
LeftRotate(PPP);
LeftRotate(PP);
}
}
}
root=P;
}
void Insert(pair<int, int> v,int ansv,int ansi)
{
Node *T=root;
if(!T)
{
root=(Node*) malloc(sizeof(Node));
root->l=NULL;
root->r=NULL;
root->p=NULL;
root->v=v;
root->sz=1;
root->ansv=ansv;
root->ansi=ansi;
return;
}
while(T)
{
if(v < (T->v) )
{
if(T->l)
{
T=T->l;
continue;
}
else
{
T->l=(Node *)malloc(sizeof(Node));
T->l->l=NULL;
T->l->r=NULL;
T->l->p=T;
T->l->v=v;
T->l->ansv=ansv;
T->l->ansi=ansi;
T->l->sz=1;
T=T->l;
break;
}
}
else
{
if(T->r)
{
T=T->r;
continue;
}
else
{
T->r=(Node *)malloc(sizeof(Node));
T->r->l=NULL;
T->r->r=NULL;
T->r->p=T;
T->r->v=v;
T->r->ansv=ansv;
T->r->ansi=ansi;
T->r->sz=1;
T=T->r;
break;
}
}
}
Node* tosplay=T;
while(T)
{
UpdateSize(T);
T=T->p;
}
Splay(tosplay);
}
Node* Find(pair<int,int> v)
{
Node *T=root;
while(T)
{
if(v==(T->v))
{
Splay(T);
return T;
}
if(v< (T->v))
{
if(T->l)
{
T=T->l;
}
else
{
Splay(T);
return NULL;
}
}
else
{
if(T->r)
{
T=T->r;
}
else
{
Splay(T);
return NULL;
}
}
}
return NULL;
}
void Erase(Node *T)
{
//printf("%d\n",root->sz);
Splay(T);
//printf("%d\n",root->sz);
if(T->l)
{
root=T->l;
root->r=T->r;
T->r->p=root;
UpdateSize(root);
}
else
root=T->r;
free(T);
if(root)root->p=NULL;
}
Node* findKth(Node *T,int K)
{
int sz=0;
if(T->l) sz=T->l->sz;
if(sz==K) return T;
if(sz>K)
return findKth(T->l,K);
else
return findKth(T->r,K-sz-1);
}
Node* findKth(int K)
{
Node* Kth=findKth(root,K);
Splay(Kth);
return Kth;
}
int R;
const int MAXN=131072;
int idx[MAXN*2];
int getmax(int l,int r)
{
l+=MAXN;
r+=MAXN;
int ans=0;
while(l<=r)
{
if(l%2==1)
ans=max(ans,idx[l++]);
if(r%2==0)
ans=max(ans,idx[r--]);
l/=2;
r/=2;
}
return ans;
}
void Query(int A,int B) //from Ath Node to Bth Node (0-based)
{
//printf("%d\n",root->sz);
int findcount=B-A+1;
Node *Ath=findKth(A);
Node *Bth=findKth(B);
//printf("%d %d %d %d\n",A,B,(Ath->v).first,(Bth->v).first);
int ansv=-1;
int ansi=-1;
pair<int,int> v=make_pair((Ath->v).first,(Bth->v).second);
//printf("%d\n",root->sz);
for(int i=0;i<findcount;i++)
{
Node *Ath=findKth(A);
if(ansv < (Ath->ansv))
{
ansv=Ath->ansv;
ansi=Ath->ansi;
}
//printf("%d\n",root->sz);
Erase(Ath);
}
int ans=getmax(v.first,v.second-1);
if(ans<R) ansv++;
Insert(v,ansv,ansi);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
::R=R;
for(int i=0;i<N;i++)
Insert(make_pair(i,i),0,i);
for(int i=0;i<N-1;i++)
idx[MAXN+i]=K[i];
for(int i=MAXN-1;i>=1;i--)
idx[i]=max(idx[2*i],idx[2*i+1]);
for(int i=0;i<C;i++)
Query(S[i],E[i]);
return root->ansi;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |