K-th zero

I am using a solution, where I store all the doors in a BST, and if door k is to be deleted then I delete the kth smallest element in the BST. Same for lookup, I search the kth smallest and print the number.

In test case 2 it is showing memory limit exceeded with only some 66-69KB memory usages. But the question says 64MB memory is allocated. Then why is this happening?
(I am using C++ to code this.)

I've used BST but still cannot optimize it... similar code on C is accepted with 0.171s 300kb but Python is processing the code way longer and TLE #14. And no solutions on python so far. Is there something that can be done?

I wrote two programs, one AC, one WA.
I run these two programs for many times but they always make
the same answer.
Is it strange?

The time limit for the problem has been corrected from 2.0 sec to 1.0 sec. The new value better reflects the original expectations for accepted solutions back from 2006. Around 40 authors have lost their AC (mostly submitted since 2017).

Mine is O(m*logn*logn)and got AC in 0.75s,958 KB.
I used a BST,a Hash table and Binary Search.
I think my algorithm is not good enough and I'm interested in how you solve this.

EM:tczw@sina.com

In seems that in C++ for set-object no operator for
standard container inquiry : N-tn element,  with log N complexity,  but should be.
With such operator problem 1439 would be very simple.
In reality  was necessary to program my own set class based on red-black trees. And N-th element to realize was very simple(hard work was balancing).
It,s not well that tree-structures of standard containers are hidden  for uses in C++.

Can anyone provide me 27th test case or tell me were am I wrong? I am using dynamic segment tree where in each node I store the count of doors in the current interval. Thanks in advance.

source code: https://ideone.com/PmG5Qb

Sorry for bad English

Help with #2 test! give example data! all data in topics my programm pass!

20 27
D5
L5
D7
L7
D6
L7
D1
L4
D11
L10
D14
L13
D5
L5
D1
D2
D3
D5
D4
L1
L2
L3
L4
L5
L6
L7
L8


6
9
10
6
14
18
10
3
6
11
14
16
17
18
20

my AC used treap as data structure and binary search for the answer. In heap I have kept numbers of initial deleted rooms. After each query I was looking for this number. And if query is 'LOOK AT', I print it, else insert in treap.
O(M * log^2K), where K is number of query 'D'
P.S.: sorry for bad English.

Edited by author 30.08.2012 18:26

Hello,

Could anyone provide me with some hint about the test 22? I keep getting WA#22.

Using Binary Indexed Tree (aka Fenwick tree) and standart System.Dictionary (dictionary bsaed on hashing).

Hint: you do not need binary search over heap!
If you're familiar with Fenwick tree's structure, you can write your own function, which'll find the smallest index in fenwick's tree with given sum.

I'm have gotten "memory limit exceeded" on test 2. I try to solve this task with Fenwick tree in Java.
But "memory allocated" value in result table is only 4.7MB. Stated memory limit is 16MB, and some of accepted solution have almost 16MB allocated (ID 3136829 for example).




Edited by author 08.05.2011 15:37

Can anybody help me with ML? I submit cartesian tree and got ML

20 7
D 9
D 7
D 6
D 1
D 2
D 3
L 2
The answer should be 4.

import java.io.*;
import java.util.*;

public class Problem_1439 implements Runnable{
    public static void main(String []args){
        new Thread(new Problem_1439()).start();
    }
    public void run(){
        try{
            reader = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
            solve();
        }catch(IOException e){
            throw new IllegalStateException(e);
        }
    }

    int nextInt()throws IOException{
        reader.nextToken();
        return (int)reader.nval;
    }

    boolean nextType()throws IOException{
        reader.nextToken();
        String s = reader.sval;
        if (s.length()!=1 && s.charAt(0)!='L' && s.charAt(0)!='D'){
            for (int i = 0; i< 1000000000;i++)System.out.println("ERORO");
        }
        return reader.sval.charAt(0)=='L';
    }

    int n, m;

    StreamTokenizer reader;

    final int MAX_N = 211111;

    class node{
        int left, right;
        int lleft, rright;
        int x, y;
        int size;

        node(){
            left = right= x = y = size =  lleft = rright = 0;
        }
    }
    node tree[];
    int g[];
    int  lt, root;
    int i, j, c, k;
    int getSize(int root){
        return (root == 0 ) ? 0: tree[root].size;
    }




    int insert(int root, int x, int y){
        if (root == 0 || tree[root].y <= y){

            lt++;
            //tree[lt] = new node();
            tree[lt].left   = 0;
            tree[lt].right  = 0;
            tree[lt].lleft  = lt;
            tree[lt].rright = lt;
            tree[lt].x = x;
            tree[lt].y = y;

            if (root > 0){
                if (tree[root].x < x)tree[lt].left = root; else tree[lt].right = root;
            }
            tree[lt].size = 1 + getSize(tree[lt].left)+getSize(tree[lt].right);

            if (tree[lt].left > 0)tree[lt].lleft = tree[tree[lt].left].lleft;
            if (tree[lt].right > 0)tree[lt].rright = tree[tree[lt].right].rright;
            return lt;
        }else if (x > tree[root].x){
            tree[root].size ++;
            tree[root].right = insert(tree[root].right, x, y);

            tree[root].rright = tree[tree[root].right].rright;
            return root;
        }else {
            tree[root].size++;
            tree[root].left = insert(tree[root].left, x, y);

            tree[root].lleft = tree[tree[root].left].lleft;
            return root;
        }
    }
    int getId(int root, int k, int min){
        if (root == 0)return k;
        int sz = getSize(tree[root].left);
        int delta = tree[root].x - (min + sz + 1);
        //if (delta < k)return getId(tree[root].right, k, min + sz + 1);
        if (delta >= k){
            if (tree[root].left == 0)return k + min;
            int lright = tree[tree[root].left].rright;
            int delta2 = tree[lright].x - (min  + sz);
            if (delta2 < k)return k + min + sz;else return getId(tree[root].left, k, min);
        }else {
            if (tree[root].right == 0)return k + min + sz + 1;
            int rleft = tree[tree[root].right].lleft;
            int delta2 = tree[rleft].x - (min + sz + 2);
            if (delta2 >= k)return k + min + sz + 1; else return getId(tree[root].right, k , min + sz + 1);
        }
    }

    void solve()throws IOException{
        n = nextInt();
        m = nextInt();
        g = new int[ MAX_N+1];
        tree = new node[MAX_N + 1];
        for (i = 0; i<=MAX_N;i++){
            tree[i] = new node();

        }


        for (i = 1; i<=MAX_N;i++){
            k = 1 + new Random().nextInt(i);
            g[i] = g[k];
            g[k] = i;
        }
        root = 0;
        lt = 0;
        j = 0;

        boolean type;
        int mind, maxd, d;
        mind = 1000000000;
        maxd = 1;
        d = 0;
        for (i = 1; i<= m;i++){
            type = nextType();
            k = nextInt();
            if (k <= mind)k = k + 0;
            else if(k + d>=maxd )k+=d;
            else
            k  = getId(root, k, 0);

            if ( type ) {//L
                System.out.println(k);
            }else if (k<=n){//D
                j++;
                root = insert(root, k, g[j]);
                d ++;
                if (k <= mind)mind = k - 1;
                if (k >= maxd)maxd = k + 1;
            }

        }

    }
}

This is my program
program preg;
var n,m,i,t,ch,e,sh,k,shh:longint;st:boolean;s:string;des,otv:array[1..100000]of longint;b:array[1..100000]of boolean;
begin
read(n);readln(m);
sh:=1;
for i:=1 to m do begin
readln(s);
if (s[1]='L') then b[sh]:=true
else b[sh]:=false;
val(s[3],ch,e);
des[sh]:=ch;sh:=sh+1;
end;
sh:=1;
for i:=2 to m+1 do begin
  if b[i-1]=false then begin
    for k:=i to m do begin
      if des[k]>=des[i-1]then begin
      shh:=0;st:=false;
        while st=false do begin
        shh:=shh+1;st:=true;
          for t:=1 to i-1 do begin
          if (des[k]+shh=des[t])and(b[t]=false)then st:=false;
          end;
        end;
      des[k]:=des[k]+shh;
      end;
    end;
  end;
  if b[i-1]=true then begin
  otv[sh]:=des[i-1];sh:=sh+1;
  end;
end;
for i:=1 to sh-1 do writeln(otv[i]);
end.