比赛 |
20120706 |
评测结果 |
AAAAAAAAAA |
题目名称 |
校草 |
最终得分 |
100 |
用户昵称 |
IMSL77 |
运行时间 |
0.000 s |
代码语言 |
Pascal |
内存使用 |
0.00 MiB |
提交时间 |
2012-07-06 11:56:19 |
显示代码纯文本
program main;
type
integer=longint;
const
maxn=110000;
var
n,m:integer;
a:array[1..maxn,1..4] of integer;
fall:array[1..maxn] of boolean;
b:array[1..maxn] of integer;
tmin:array[0..maxn] of integer;
procedure Fopen;
begin
assign(input,'hjjhvf.in');
reset(input);
assign(output,'hjjhvf.out');
rewrite(output);
end;
procedure Fclose;
begin
close(input);
close(output);
end;
procedure Init;
var
i:integer;
begin
readln(n);
for i:=1 to n do readln(a[i,1],a[i,2],a[i,3],a[i,4]);
end;
procedure QSort(p,l,r:integer);
var
i,j:integer;
t,x:integer;
begin
i:=l; j:=r;
x:=a[b[(l+r) shr 1],p];
repeat
while a[b[i],p]<x do inc(i);
while a[b[j],p]>x do dec(j);
if i<=j then
begin
t:=b[i]; b[i]:=b[j]; b[j]:=t;
inc(i); dec(j);
end;
until i>j;
if l<j then QSort(p,l,j);
if i<r then QSort(p,i,r);
end;
function lowbit(x:integer):integer;
begin
exit(x and (-x));
end;
function min(a,b:integer):integer;
begin
if a<b then exit(a) else exit(b);
end;
function query(k:integer):integer;
var
res:integer;
begin
res:=n shl 1;
while k>0 do
begin
res:=min(res,tmin[k]);
dec(k,lowbit(k));
end;
exit(res);
end;
procedure update(k,x:integer);
begin
while k<=n do
begin
tmin[k]:=min(tmin[k],x);
inc(k,lowbit(k));
end;
end;
procedure GoOut(p1,p2,p3:integer);
var
i,q:integer;
begin
for i:=1 to n do b[i]:=i;
QSort(p1,1,n);
for i:=0 to n do tmin[i]:=n shl 1;
for i:=1 to n do
begin
q:=query(a[b[i],p2]-1);
if q<a[b[i],p3] then fall[b[i]]:=true;
update(a[b[i],p2],a[b[i],p3]);
end;
end;
procedure Solve;
var
i:integer;
begin
fillchar(fall,sizeof(fall),false);
GoOut(1,2,3);
GoOut(2,3,4);
GoOut(1,3,4);
GoOut(1,2,4);
m:=0;
for i:=1 to n do if fall[i] then inc(m);
writeln(m);
for i:=1 to n do if fall[i] then writeln(i);
end;
begin
Fopen;
Init;
Solve;
Fclose;
end.