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

数组为什么要开1500000。。。。。。才能过,《贴代码》。。做了好久啊

Posted by 1083595345 at 2015-08-02 13:55:58 on Problem 2828
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int maxn=1500000;//数组为何开这么大。。。

int tree[maxn],sum[maxn],num[maxn][2],n;

int sum_insert(int l,int r,int rt)
{
    if(l==r) return sum[rt]=1;
    return sum[rt]=sum_insert(l,(l+r)/2,rt*2)+sum_insert((l+r)/2+1,r,rt*2+1);
}

int insert(int pos,int val,int rt)
{
    if(sum[rt*2]==-1) {tree[rt]=val;return sum[rt]-=1;}
    if(sum[rt*2]<pos) return sum[rt]=sum[rt*2]+insert(pos-sum[rt*2],val,rt*2+1);
    else return sum[rt]=sum[rt*2+1]+insert(pos,val,rt*2);
}

//int push_up(int l,int r,int rt) { if(l==r) return sum[rt]=tree[rt]?0:1; return sum[rt]=push_up(l,(l+r)/2,rt*2)+push_up((l+r)/2+1,r,rt*2+1); }

void output(int l,int r,int rt)
{
    if(l==r) {printf("%d",tree[rt]);return ;}
    output(l,(l+r)/2,rt*2);printf(" ");
    output((l+r)/2+1,r,rt*2+1);
}

int main()
{
    while(~scanf("%d",&n)){
        memset(sum,-1,sizeof sum),memset(tree,0,sizeof tree);
        sum_insert(1,n,1);
        for(int i=0;i<n;i++) scanf("%d%d",&num[i][0],&num[i][1]);
        for(int i=0;i<n;i++) num[i][0]+=1;
        for(int i=n-1;i>=0;i--) insert(num[i][0],num[i][1],1);//push_up(1,n,1);贡献几次超时,其实可以同时完成
        output(1,n,1); printf("\n");
    }

    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