GCJ2013 Round1C The Great Wall https://code.google.com/codejam/contest/2437488/dashboard#s=p2

TheGreatWall.java

package com.polysfactory.gcj2013;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class TheGreatWall {
    static class Data {
        int n;
        int w;
        int e;
        int height;
        int firstDay;
        int dday;
        int ddist;
        int dheight;
    }

    static class Attack implements Comparable<Attack> {
        int w;
        int e;
        int day;
        int height;

        @Override
        public int compareTo(Attack o) {
            return this.day - o.day;
        }

    }

    static class SegmentTree {
        int segmentTree[];
        final int n;
        final int height;
        final int lastRowOffset;

        public SegmentTree(int size) {
            this.height = log((size * 2) - 1, 2) + 1;
            this.n = (int) (Math.pow(2, this.height - 1));
            this.segmentTree = new int[(int) (Math.pow(2, this.height))];
            this.lastRowOffset = (int) (Math.pow(2, this.height - 1)) - 1;
        }

        static int log(int x, int base) {
            return (int) (Math.log(x) / Math.log(base));
        }

        public void update(int leftIndex, int rightIndex, int newValue) {
            for (int i = leftIndex; i <= rightIndex; i++) {
                int nodeIndex = lastRowOffset + i;
                if (segmentTree[nodeIndex] >= newValue) {
                    // no need to update
                    continue;
                }
                segmentTree[nodeIndex] = newValue;
                while (nodeIndex > 0) {
                    nodeIndex = (nodeIndex - 1) / 2;
                    int leftChild = nodeIndex * 2 + 1;
                    int rightChild = nodeIndex * 2 + 2;
                    segmentTree[nodeIndex] = Math.min(segmentTree[leftChild],
                            segmentTree[rightChild]);
                }
            }
        }

        public int query(int leftIndex, int rightIndex) {
            return queryRec(leftIndex, rightIndex, 0, n - 1, 0);
        }

        private int queryRec(final int targetLeft, final int targetRight, int nodeLeft,
                int nodeRight, int nodeIndex) {
            if (targetRight < nodeLeft || targetLeft > nodeRight) {
                return Integer.MAX_VALUE;
            }
            if (targetLeft <= nodeLeft && targetRight >= nodeRight) {
                // current range is completely included in the target range
                return segmentTree[nodeIndex];
            }
            int leftChildMax = (nodeLeft + nodeRight) / 2;

            int leftMin = queryRec(targetLeft, targetRight, nodeLeft, leftChildMax,
                    nodeIndex * 2 + 1);
            int rightMin = queryRec(targetLeft, targetRight, leftChildMax + 1, nodeRight,
                    nodeIndex * 2 + 2);
            return Math.min(leftMin, rightMin);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        for (int tt = 0; tt < T; tt++) {
            int n = scanner.nextInt();
            List<Data> datas = new ArrayList<Data>();
            Set<Integer> points = new TreeSet<Integer>();
            int attackCount = 0;
            for (int i = 0; i < n; i++) {
                Data data = new Data();
                data.firstDay = scanner.nextInt();
                data.n = scanner.nextInt();
                data.w = scanner.nextInt();
                data.e = scanner.nextInt();
                data.height = scanner.nextInt();
                data.dday = scanner.nextInt();
                data.ddist = scanner.nextInt();
                data.dheight = scanner.nextInt();
                datas.add(data);
                int w = data.w;
                int e = data.e;
                for (int j = 0; j < data.n; j++) {
                    points.add(w);
                    points.add(e);

                    w += data.ddist;
                    e += data.ddist;
                    attackCount++;
                }
            }

            List<Integer> pointList = new ArrayList<Integer>(points);
            Map<Integer, Integer> positionMap = new HashMap<Integer, Integer>();
            for (int i = 0; i < pointList.size(); i++) {
                positionMap.put(pointList.get(i), i);
            }

            List<Attack> attacks = new ArrayList<Attack>(attackCount);
            for (Data data : datas) {
                int w = data.w;
                int e = data.e;
                int h = data.height;
                int d = data.firstDay;

                for (int j = 0; j < data.n; j++) {
                    Attack attack = new Attack();
                    attack.w = positionMap.get(w);
                    attack.e = positionMap.get(e) - 1;
                    attack.day = d;
                    attack.height = h;
                    attacks.add(attack);

                    w += data.ddist;
                    e += data.ddist;
                    h += data.dheight;
                    d += data.dday;
                }
            }

            Collections.sort(attacks);
            SegmentTree segmentTree = new SegmentTree(pointList.size() - 1);

            int score = 0;
            int i = 0;
            int attackNum = attacks.size();
            while (i < attackNum) {
                Attack attack = attacks.get(i);
                int k = i + 1;
                while (k < attackNum && (attacks.get(k).day == attack.day)) {
                    k++;
                }
                for (int j = i; j < k; j++) {
                    Attack a = attacks.get(j);
                    int min = segmentTree.query(a.w, a.e);
                    if (min < a.height) {
                        score++;
                    }
                }
                for (int j = i; j < k; j++) {
                    Attack a = attacks.get(j);
                    segmentTree.update(a.w, a.e, a.height);
                }
                i = k;
            }
            System.out.println("Case #" + (tt + 1) + ": " + score);
        }
    }
}