Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- public class RocketFuel {
- public static class Record {
- int spaceshipId;
- long time;
- boolean isStart;
- public Record(int spaceshipId, long time, boolean isStart){
- this.spaceshipId = spaceshipId;
- this.time = time;
- this.isStart = isStart;
- }
- }
- public static class Score {
- int score;
- int spaceshipId;
- public Score(int score, int spaceshipId) {
- this.score = score;
- this.spaceshipId = spaceshipId;
- }
- }
- // use binary index tree to do range sum query
- public static class BIT {
- private int[] tree;
- public BIT(int n) {
- tree = new int[n + 1];
- }
- public int getSum(int idx) {
- idx += 1;
- int sum = 0;
- while (idx > 0) {
- sum += tree[idx];
- idx = getParent(idx);
- }
- return sum;
- }
- // [start, end] both inclusive
- public int rangeQuery(int start, int end) {
- if (start == 0) {
- return getSum(end);
- }
- return getSum(end) - getSum(start);
- }
- private int getParent(int idx) {
- return idx - (idx & (-idx));
- }
- public void update(int idx, int val) {
- idx += 1;
- while (idx < tree.length) {
- tree[idx] += val;
- idx = getNext(idx);
- }
- }
- private int getNext(int idx) {
- return idx + (idx & (-idx));
- }
- }
- public static void main(String args[] ) throws Exception {
- Scanner sc = new Scanner(System.in);
- int N = sc.nextInt();
- List<Record> recordList = new ArrayList<>();
- for (int i = 0; i < N; i++) {
- int spaceshipId = sc.nextInt();
- long startTime = sc.nextLong();
- long endTime = sc.nextLong();
- recordList.add(new Record(spaceshipId, startTime, true));
- recordList.add(new Record(spaceshipId, endTime, false));
- }
- Collections.sort(recordList, new Comparator<Record>(){
- @Override
- public int compare(Record r1, Record r2) {
- return r1.time < r2.time? -1 : 1;
- }
- });
- Map<Integer, Integer> idToRec = new HashMap<>();
- BIT tree = new BIT(recordList.size());
- List<Score> result = new ArrayList<>();
- // rnum -> record number
- for (int rnum = 0; rnum < recordList.size(); rnum++) {
- Record currentRecord = recordList.get(rnum);
- // if this is a start record.
- if (currentRecord.isStart) {
- idToRec.put(currentRecord.spaceshipId, rnum);
- } else {
- // else this is an end record
- int startRec = idToRec.get(currentRecord.spaceshipId);
- int score = tree.rangeQuery(startRec, rnum);
- result.add(new Score(score, currentRecord
- .spaceshipId));
- tree.update(startRec, 1);
- }
- }
- Collections.sort(result, new Comparator<Score>() {
- @Override
- public int compare(Score s1, Score s2) {
- if (s1.score == s2.score) {
- return s1.spaceshipId < s2.spaceshipId ? -1 : 1;
- } else {
- return s1.score < s2.score ? -1 : 1;
- }
- }
- });
- for (Score s : result) {
- System.out.print(s.spaceshipId + " " + s.score);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement