Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

水题!(有AC代码)

Posted by yc5_yc at 2012-08-27 21:34:52 on Problem 2828
In Reply To:没有1A的惨痛教训 Posted by:5D6D2 at 2012-08-27 21:31:54
感谢一下网址开导我:http://blog.csdn.net/logic_nut/article/details/4498825
这位好心人的解释清晰明了!
贴代码:
#include <cstdio>
using namespace std;
const int NMax=200100;
int N,L,P[NMax],V[NMax];
struct node {
    int l,r,m,cnt,num;
    node *left,*right;
}*Tree,pool[NMax*3];
void Build(node *p,int x,int y) {
    p->l=x;p->r=y;p->m=(x+y)>>1;p->cnt=(p->r-p->l+1);p->left=p->right=NULL;
    if(x<y) {
        p->left=&pool[L++];p->right=&pool[L++];
        Build(p->left,x,p->m);Build(p->right,p->m+1,y);
    }
}
int calc(node *p,int x) {
    if(p->l==p->r) {
        p->cnt--;
        return p->r;
    }
    int tmp;
    if(p->left->cnt>=x) tmp=calc(p->left,x);
    else tmp=calc(p->right,x-p->left->cnt);
    p->cnt=p->left->cnt+p->right->cnt;
    return tmp;
}
void Let(node *p,int x,int y) {
    if(p->l==p->r) {
        p->num=y;
        return ;
    }
    if(x<=p->m) Let(p->left,x,y);
    else Let(p->right,x,y);
}
int Search(node *p,int x) {
    if(p->l==p->r) return p->num;
    if(x<=p->m) return Search(p->left,x);
    else return Search(p->right,x);
}
int main()
{
    while(scanf("%d",&N)!=EOF) {
        L=0;Tree=&pool[L++];
        Build(Tree,1,N);
        for(int i=1;i<=N;i++)
            scanf("%d%d",P+i,V+i);
        for(int i=N;i>=1;i--) {
            int x=calc(Tree,P[i]+1);
            //printf("%d\n",x);
            Let(Tree,x,V[i]);
        }
        for(int i=1;i<N;i++) printf("%d ",Search(Tree,i));
        printf("%d\n",Search(Tree,N));
    }
    //getchar();getchar();
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator