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

用树状数组总是超时,帮忙看看啊,谢谢了。。。

Posted by richardxx at 2006-12-27 17:30:32 on Problem 2828
#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