ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1439. Battle with You-Know-Who

my prog alway WA#22. What is test22, or some hint, here my code
Posted by xurshid_n 25 Aug 2009 21:31
import java.io.*;
import java.util.*;

public class Problem_1439 implements Runnable{
public static void main(String []args){
}
public void run(){
try{
solve();
}catch(IOException e){
throw new IllegalStateException(e);
}
}

int nextInt()throws IOException{
}

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

int n, m;

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;
}

}

}
}