Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
4.6 kB
51
Indexable
Never
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Solution{
    private final static int CMD_INIT = 1;
    private final static int CMD_ARRIVE = 2;
    private final static int CMD_LEAVE = 3;
    
    private final static UserSolution usersolution = new UserSolution();
    
    private static boolean run(BufferedReader br) throws Exception {
        int q = Integer.parseInt(br.readLine());
        
        int n, mid;
        int cmd, ans, ret =0;
        boolean okay = false;
        
        for (int i=0; i<q;i++){
            StringTokenizer sr = new StringTokenizer(br.readLine(), " ");
            cmd = Integer.parseInt(st.nextToken());
            switch(cmd){
                case CMD_INIT:
                    n = Integer.parseInt(st.nextToken());
                    usersolution.int();
                    okay=true;
                    break;
                case CMD_ARRIVE:
                    mid = Integer.parseInt(st.nextToken());
                    ans = Integer.parseInt(st.nextToken());
                    ret = Integer.parseInt(st.nextToken());
                    if(ret != ans) okay = true;
                    break;
                case CMD_LEAVE:
                    mid = Integer.parseInt(st.nextToken());
                    ans = Integer.parseInt(st.nextToken());
                    ret = Integer.parseInt(st.nextToken());
                    if(ret != ans) okay = true;
                    break;
                default:
                    okay = true;
                    break;
            }
        }
        return okay;
    }
    
    public static void main(String[] args) throws Exception {
        int TC, MARK;
        
        System.setIn(new java.io.FileInputStream("sample_input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine(),  " ");
        TC = Integer.parseInt(st.nextToken());
        MARK = Integer.parseInt(st.nextToken());
        
        for (int tc = 1; tc<= TC;tc++){
            int score = run(br) ? MARK :0;
            System.out.println("#"+tc+" "+score);
        }
        br.close();
    }     
    
}


import java.util.*;

class Node {
    int begin, end, size;
    Node (int b, int e){
        this.begin = b;
        this.end = e;
        this.size = end-begin+1;
    }
}

class CmpSize implements Comparator<Node> {
    @Override
    public int compare(Node o1, Node o2){
        if(o1.size == o2.size) return o1.begin-o2.begin;
        return o1.size-o2.size;
    }
}
class CmpBegin implements Comparator<Node> {
    @Override
    public int compare(Node o1, Node o2){
        return o1.begin-o2.begin;
    }
}

class UserSolution{
    private TreeSet<Node> treeSize;
    private TreeSet<Node> treeBegin;
    private HashMap<Integer, Integer> hashID;
    
    int N, empty;
    
    public void init(int N){
        this.N = N;
        empty = N;
        treeSize = new TreeSet<Node>(new CmpSize);
        treeBegin = new TreeSet<Node>(new CmpBegin);
        
        Node n = new Node(1, N);
        treeSize.add(n);
        treeBegin.add(n);
        return;
    }
    
    public void arrive(int mId){
        empty--;
        Node max = treeSize.poolFirst();
        treeBegin.remove(max);
        
        int set = (max.begin+max.end) / 2;
        
        if(max.begin==1) set = 1;
        else if(max.end==N) set = N;
        
        if(set>max.begin){
            Node temp = new Node(max.begin, set-1);
            treeBegin.add(temp);
            treeSize.add(temp);
        }
        if(set<max.begin){
            Node temp = new Node(set+1,max.end);
            treeBegin.add(temp);
            treeSize.add(temp);
        }
        hashID.put(temp);
        return set;
    }
    
    public void leave(int mId){
        empty++;
        int cut = hashID.remove(mId);
        Node tmp = new Node(cut,cut);
        Node tHight = treeBegin.higher(tmp);
        Node tLow = treeBegin.lower(tmp);
        
        if (tLow != null && tLow.end == cut-1){
            treeSize.remove(tLow);
            treeBegin.remove(tLow);
            tmp.begin = tLow.begin;
            tmp.size = tmp.end-tmp.begin+1;
        }
        if (tHight != null && tHight.begin == cut+1){
            treeSize.remove(tHight);
            treeBegin.remove(tHight);
            tmp.end = tHight.end;
            tmp.size = tmp.end-tmp.begin+1;
        }
        treeBegin.add(tmp);
        treeSize.add(tmp);
        
        return empty;
    }


}


1 100
12
1 8
2 200 1
2 100 8
2 700 4
2 600 6
3 200 5
2 300 1
2 800 2
2 200 3
3 600 3
3 100 4
2 400 8