Can anyone tell me what is test number 6??? I used BIT and i get WA at test numebr 6... Help me please

Could anyone show me what the input for test #5 is? I can't figure out why my solution fails this test case. Thanks a lot.

I have tried using bucket search( N*sqrt(N)) and segment tree based search( N*log(N)), but still only get AC in 0.1s

Anyone can shed some light on this? I have seen someone mentioned mergsort, is this the point?

var
   i, j, q, key, n, k, k1, max, row : integer;
   a : array [1..10000] of integer;

begin
  read(n, k); row := 1;  max := 0;
  for k1 := 1 to k do
    begin
  for i := 1 to n do
  read(a[i]);
q := 0;
For j:=2 to n do
Begin
   Key:=a[j];
   I:=j-1;
   While (i>0) and (A[i]>key) do
       Begin
           A[i+1]:=a[i];   inc(q);
           Dec(i);
       End;
   A[i+1]:=key;
End;
if max < q then begin max := q;  row := k1;  end;
end;
writeLn(row);
end.

at first i wrote bst,and i got tle at testcase 3.
Now i know that i should have written SBT such as treap.

Can someone give me test case..i use insertion sort to calculate number of jumps.

Could anybody suggest the 3-rd test???? i don't know my mistake. :-(

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <math.h>

using namespace std;

class Summator {
private:
    vector<bool> l;
    vector<int> b;
    int size;
    int b_size,b_count;
public:
    void init (int _size) {
        size=_size;
        b_size=(int)pow(size,0.5);
        b_count=size/b_size+1;
        l.resize(size);
        b.resize(b_count);
    }
    void reset() {
        for(int i=0;i<size;i++)
            l[i]=false;
        for(int i=0;i<b_count;i++)
            b[i]=0;
    }
    int findsum(int a) {
        int p=a/b_size;
        if (a%b_size!=0)
            p++;
        int res=0;
        for(int i=p+1;i<b_count;i++)
            res+=b[i];
        a-=(--p)*b_size;
        for(int i=a;i<=b_size;i++)
            if ((p*b_size+i<size)&&(l[p*b_size+i]))
                res++;
        return res;
    }
    void add(int pos) {
        l[pos]=true;
        int p=pos/b_size;
        if (pos%b_size!=0)
            p++;
        b[p]++;
    }
};

int main () {
    #ifndef ONLINE_JUDGE
        ifstream cin("input.txt");
    #endif
    int n,k,res,max=0;
    cin>>n>>k;
    Summator s;
    s.init(n+1);
    for(int t=0;t<k;t++){
        int rs=0,p;
        s.reset();
        for(int i=0;i<n;i++) {
            cin>>p;
            rs+=s.findsum(p+1);
            s.add(p);
        }
        if (rs>max) {
            max=rs;
            res=t+1;
        }
    }
    cout<<res<<endl;
    return 0;
}

Edited by author 16.04.2007 21:18

Program p1090;

Const
  Maxn=12000;

Var
  Ans,good,p,n,m,i,j,k,fin:Longint;
  A:array[0..Maxn] of Longint;
  L:array[0..Maxn] of Longint;

Procedure Find(left,right,p:Longint);
Var
  mid:Longint;
Begin
  If left>right Then Exit;
  If Left=Right Then
    Begin
      If (L[left]<p) And (L[left]<>0) And (Left>good) Then Good:=left;
      Exit;
    End;
  mid:=(left+right) div 2;
  If (L[mid]<P) And (L[mid]<>0) And (mid>good) Then
    Begin
      Good:=mid;Find(mid+1,right,p);
    End
  Else Find(left,mid-1,p);
End;

Begin
    Readln(N,M);
  Fin:=Maxlongint div 2;
  For i:=1 to m Do
    Begin
      For j:=1 to n Do
        Read(A[j]);
      Readln;
      Fillchar(L,sizeof(L),0);
      Ans:=0;
      For j:=1 to n Do
        Begin
          Good:=0;
          Find(1,Ans,A[j]);
          If good+1>Ans Then Ans:=good+1;
          If (L[good+1]=0) or (L[good+1]>A[j]) Then L[good+1]:=A[j];
        End;
      If Ans<fin Then
        Begin
          Fin:=Ans;P:=I;
        End;
    End;
  WRiteln(p);
  End.

I change languege from Java to cpp.It is very small time limit for Java.

post the fifth test or a similar one please

if they are not too long

Can somebody give me some ideas? What algorithm to use?

LineTree
But in Init,You must let ans be 1.maybe there is a test,the test's each line is 1,2,3,4......

Who can give me an AC program?