Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
[VOJ] Mã nguồn #226 - bài NKINV theo hướng chia để trị - Pascal version
Ngày: 29-01-2013
Cập nhật: 29-01-2013
Người gửi: quandum
Ngôn ngữ: Pascal
Xem: 50

Điểm: 0.0/5 (0 Phiếu)


{
coder: quandum - VNOI
Problem: http://vn.spoj.pl/problems/NKINV/
count_inv(u,v) la so day nghich the cua day a[l..r], 
Dat mid=(u+v) div 2
count_inv(u,v)=count_inv(u,mid)+count_inv(mid+1,v)+z
voi z la so cap nghich the nam o 2 ben mid.
Tuong ung voi so cap nghich the a[i] a[j] cua 3 truong hop:
- u<=i<j<=mid    => x:=count_inv(u,mid);
- mid<i<j<=v     => y:=count_inv(mid+1,v);
- u<=i<=mid<j<=v => z
Dat L=a[u..mid] và R=a[mid+1..v] thi z chinh la so cap (i,j) L[i]>R[j]
}
const  maxn=100000;
var
     a:array[1..maxn+2]of longint;
     l,r:array[0..(maxn div 2)+2]of longint;
     n,i:longint;        kq:int64;
function count_inv(u,v:longint):int64;
var  x,y,z:int64;
     i,j,mid,nl,nr:longint;
begin
    if (u>=v) then begin
          count_inv:=0;
          exit;
    end;
    mid:=(v+u) div 2;
    x:=count_inv(u,mid);           y:=count_inv(mid+1,v);
    for i:=u to mid do l[i-u]:=a[i];
    for j:=mid+1 to v do r[j-(mid+1)]:=a[j];
    nl:=mid-u+1;    nr:=v-mid;     r[nr]:=maxlongint;
    z:=0;           j:=0;
    for i:=0 to nl-1 do begin
          for j:=j to nr do begin
               if (l[i]>r[j]) then a[u+i+j]:=r[j]
               else break;
          end;
          a[u+i+j]:=l[i];
          z:=z+j;
    end;
    for j:=j to nr-1 do a[u+nl+j]:=r[j];
    count_inv:=x+y+z;
end;
begin
    assign(input,'');          reset(input);
    assign(output,'');         rewrite(output);
    readln(n);                 for i:=1 to n do read(a[i]);
    kq:=count_inv(1,n);    writeln(kq);
    close(input);        close(output);
end.