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大学生程序设计竞赛训练》暑期课面向全球招生!

好象求rank时复杂度高了些啊

Posted by daringQQ at 2006-12-27 17:47:17 on Problem 2828
In Reply To:用树状数组总是超时,帮忙看看啊,谢谢了。。。 Posted by:richardxx at 2006-12-27 17:30:32
> #include <stdio.h>
> #include <string.h>
> 
> #define N 2<<18
> 
> struct item
> {
>   int pos;
>   int value;
> };
> 
> struct item input[N];
> int c[N];
> int a[N];
> int n;
> 
> void init()
> {
>   memset(a,0,sizeof(a));
>   memset(c,0,sizeof(c));
> }
> 
> int low_bit(int x)
> {
>   return x&(x^(x-1));
> }
> 
> int get_sum(int x)
> {
>   int res=0;
>   
>   while (x>0) {
>     res+=c[x];
>     x-=low_bit(x);
>   }
>   return res;
> }
> 
> void add(int x)
> {
>   while (x<=n) {
>     c[x]+=1;
>     x+=low_bit(x);
>   }
> }
> 
> void solve()
> {
>   int i,v;
>   int t,temp;
> 
>   for (i=n-1;i>-1;--i) {
>     v=input[i].pos;
>     t=get_sum(v);
>     while (v+t<=n && a[v+t]) t=get_sum(v+t);
>     a[v+t]=input[i].value;
>     add(v+t);
>   }
>   for (i=1;i<=n;++i)
>     printf("%d ",a[i]);
>   putchar('\n');
> }
> 
> int main()
> {
>   int i;
> 
>   while (scanf("%d",&n)!=EOF) {
>     init();
>     for (i=0;i<n;++i) {
>       scanf("%d %d",&input[i].pos,&input[i].value);
>       input[i].pos++;
>     }
>     solve();
>   }
> 
>   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