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

注意事项以及一些想法。

Posted by The_Dawn at 2011-07-14 16:26:03 on Problem 3277
1、不止ans,tree的左右区间也要开到int64,数据坑爹。
2、因为40000条线,所以是80000的点,所以树应该开到400000左右。

discuss里有一些关于什么区间半开半闭什么的东西,我AC了以后也没弄懂是什么意思。本人理解能力不够的缘故吧。

不过本题中确实会用到spread函数(懒操作)。而且每个点x应该代表的是线段[x,x+1),这可能就是所谓的半开半闭区间吧。
具体处理方法就是,其他的都不变,在每次change的时候将区间[st,ed]的ed减1。
然后最后算总面积的时候(axis[tree[w].r+1]-axis[tree[w].l])*tree[w].h就可以了。

另,usaco 2007 open的数据网上可以搜到的...

附pascal代码一份


type
  node=record
    l,r,h,cover:int64;
  end;

var
  n,i,j,k,st,ed,h:longint;
  ans:int64;
  high,verl,verr:array[0..40001]of longint;
  axis:array[0..90000]of longint;
  tree:array[0..400000]of node;

procedure init;
  begin
    readln(n);
    for i:=1 to n do
      begin
        readln(verl[i],verr[i],high[i]);
        axis[i]:=verl[i];
        axis[i+n]:=verr[i];
      end;
  end;

procedure sort(l,r:longint);
  var
    i,j,x,y:longint;
  begin
    i:=l;j:=r;
    x:=high[(l+r)shr 1];
    repeat
      while high[i]<x do inc(i);
      while high[j]>x do dec(j);
      if not (i>j) then
        begin
          y:=high[i];high[i]:=high[j];high[j]:=y;
          y:=verl[i];verl[i]:=verl[j];verl[j]:=y;
          y:=verr[i];verr[i]:=verr[j];verr[j]:=y;
          inc(i);dec(j);
        end;
    until i>j;
    if l<j then sort(l,j);
    if i<r then sort(i,r);
  end;

procedure sortaxis(l,r:longint);
  var
    i,j,x,y:longint;
  begin
    i:=l;j:=r;
    x:=axis[(l+r)shr 1];
    repeat
      while axis[i]<x do inc(i);
      while axis[j]>x do dec(j);
      if not (i>j) then
        begin
          y:=axis[i];axis[i]:=axis[j];axis[j]:=y;
          inc(i);dec(j);
        end;
    until i>j;
    if l<j then sortaxis(l,j);
    if i<r then sortaxis(i,r);
  end;

function map(x:longint):longint;
  var
    mid,l,r:longint;
  begin
    l:=1;r:=2*n;
    while l<=r do
      begin
        mid:=(l+r)shr 1;
        if axis[mid]=x then exit(mid);
        if x>axis[mid] then l:=mid+1 else r:=mid;
      end;
  end;

procedure build(w,l,r:longint);
  var
    mid:longint;
  begin
    tree[w].l:=l;tree[w].r:=r;
    if l>=r then exit;
    mid:=(l+r)shr 1;
    build(2*w,l,mid);
    build(2*w+1,mid+1,r);

  end;

procedure spread(w:longint);
  begin
    tree[w].cover:=0;
    tree[2*w].h:=tree[w].h;
    tree[2*w+1].h:=tree[w].h;
    tree[2*w].cover:=1;
    tree[2*w+1].cover:=1;
  end;

procedure change(w:longint);
  var
    mid:longint;
  begin
    if (st<=tree[w].l)and(tree[w].r<=ed) then
      begin
        tree[w].h:=high[i];
        tree[w].cover:=1;
        exit;
      end;
    if tree[w].cover=1 then spread(w);
    mid:=(tree[w].l+tree[w].r)shr 1;
    if st<=mid then change(2*w);
    if mid<ed then change(2*w+1);
  end;

procedure sum(w:longint);
  begin
    if (tree[w].l=0)or(tree[w].l>tree[w].r) then exit;
    if tree[w].cover=1 then
      begin
        ans:=ans+(axis[tree[w].r+1]-axis[tree[w].l])*tree[w].h;
        exit;
      end;
    sum(2*w);
    sum(2*w+1);
  end;


begin
  //assign(input,'1.txt');
  //assign(output,'2.txt');
  //reset(input);rewrite(output);

  init;
  sort(1,n);
  sortaxis(1,2*n);
  build(1,1,2*n);
  for i:=1 to n do
    begin
     st:=map(verl[i]);
     ed:=map(verr[i])-1;
     change(1);
    end;
  sum(1);
  writeln(ans);

  //close(input);close(output);
end.

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