- 河蟹王国
- 2009-10-06 21:34:37 @
program vijos1659;
type code = record
cost,l,r : longint;
end;
var max,z,x,y,k,n,m,tot,i,po : longint;
tree : array[1..300001] of code;
jia : array[1..300001] of longint;
procedure build(x,y,t:longint);
var mid,p : longint;
begin
if x = y then
begin
readln(p);
tree[t].l := x;
tree[t].r := x;
tree[t].cost := p;
exit;
end;
mid := (x + y) shr 1;
build(x,mid,t*2);
build(mid+1,y,t*2+1);
tree[t].cost := tree[t shl 1].cost;
if tree[t shl 1 + 1].cost > tree[t].cost then
tree[t].cost := tree[t shl 1 + 1].cost;
tree[t].l := x;
tree[t].r := y;
end;
procedure add(x,y,t,p:longint);
var mid : longint;
begin
if (tree[t].l=x) and (tree[t].r = y) then
begin
jia[t] := jia[t] + p;
exit;
end;
mid := (tree[t].l + tree[t].r) shr 1;
if y mid then add(x,y,t*2+1,p) else
begin
add(x,mid,t*2,p);
add(mid+1,y,t*2+1,p);
end;
if tree[t * 2].cost +jia[t*2] > tree[t].cost then
tree[t].cost := tree[t * 2].cost + jia[t*2];
if tree[t * 2 + 1].cost + jia[t*2+1] > tree[t].cost then
tree[t].cost := tree[t * 2 + 1].cost + jia[t * 2 + 1];
end;
procedure find(x,y,t,p:longint);
var mid : longint;
begin
if (tree[t].l = x) and (tree[t].r = y) then
begin
if p + jia[t] + tree[t].cost > max then
max := p + jia[t] + tree[t].cost;
exit;
end;
mid := (tree[t].l + tree[t].r) shr 1;
if y mid then find(x,y,t*2+1,p+jia[t]) else
begin
find(x,mid,t*2,p+jia[t]);
find(mid+1,y,t*2+1,p+jia[t]);
end;
end;
begin
readln(n);
build(1,n,1);
readln(m);
for i := 1 to m do
begin
read(k);
if k = 2 then
begin
readln(x,y);
max := -maxlongint;
find(x,y,1,0);
writeln(max);
end else
begin
readln(x,y,z);
add(x,y,1,z);
end;
end;
end.
我自己随机了数据,和某大牛对拍完全一样啊。。。。。(有cena为证,天地良心啊。。。。orz。)
为什么在vijos上交了n次都是0分啊。。到底输入输出啥苛刻的地方啊。。我明明拍了列,,,不至于0分吧。。哪位大牛能不能帮我解答解答,,
1 条评论
-
wajiyu LV 9 @ 2009-10-07 10:42:26
p1659
貌似输入要用 READ
输出要用 WRITE
- 1