Advertisement
Guest User

Untitled

a guest
Oct 21st, 2016
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.54 KB | None | 0 0
  1. import java.util.*;
  2.  
  3. public class RocketFuel {
  4. public static class Record {
  5. int spaceshipId;
  6. long time;
  7. boolean isStart;
  8. public Record(int spaceshipId, long time, boolean isStart){
  9. this.spaceshipId = spaceshipId;
  10. this.time = time;
  11. this.isStart = isStart;
  12. }
  13. }
  14. public static class Score {
  15. int score;
  16. int spaceshipId;
  17. public Score(int score, int spaceshipId) {
  18. this.score = score;
  19. this.spaceshipId = spaceshipId;
  20. }
  21. }
  22. // use binary index tree to do range sum query
  23. public static class BIT {
  24. private int[] tree;
  25. public BIT(int n) {
  26. tree = new int[n + 1];
  27. }
  28. public int getSum(int idx) {
  29. idx += 1;
  30. int sum = 0;
  31. while (idx > 0) {
  32. sum += tree[idx];
  33. idx = getParent(idx);
  34. }
  35. return sum;
  36. }
  37. // [start, end] both inclusive
  38. public int rangeQuery(int start, int end) {
  39. if (start == 0) {
  40. return getSum(end);
  41. }
  42. return getSum(end) - getSum(start);
  43. }
  44. private int getParent(int idx) {
  45. return idx - (idx & (-idx));
  46. }
  47. public void update(int idx, int val) {
  48. idx += 1;
  49. while (idx < tree.length) {
  50. tree[idx] += val;
  51. idx = getNext(idx);
  52. }
  53. }
  54. private int getNext(int idx) {
  55. return idx + (idx & (-idx));
  56. }
  57.  
  58. }
  59. public static void main(String args[] ) throws Exception {
  60. Scanner sc = new Scanner(System.in);
  61. int N = sc.nextInt();
  62. List<Record> recordList = new ArrayList<>();
  63. for (int i = 0; i < N; i++) {
  64. int spaceshipId = sc.nextInt();
  65. long startTime = sc.nextLong();
  66. long endTime = sc.nextLong();
  67. recordList.add(new Record(spaceshipId, startTime, true));
  68. recordList.add(new Record(spaceshipId, endTime, false));
  69. }
  70. Collections.sort(recordList, new Comparator<Record>(){
  71. @Override
  72. public int compare(Record r1, Record r2) {
  73. return r1.time < r2.time? -1 : 1;
  74. }
  75. });
  76. Map<Integer, Integer> idToRec = new HashMap<>();
  77. BIT tree = new BIT(recordList.size());
  78. List<Score> result = new ArrayList<>();
  79. // rnum -> record number
  80. for (int rnum = 0; rnum < recordList.size(); rnum++) {
  81. Record currentRecord = recordList.get(rnum);
  82. // if this is a start record.
  83. if (currentRecord.isStart) {
  84. idToRec.put(currentRecord.spaceshipId, rnum);
  85. } else {
  86. // else this is an end record
  87. int startRec = idToRec.get(currentRecord.spaceshipId);
  88. int score = tree.rangeQuery(startRec, rnum);
  89. result.add(new Score(score, currentRecord
  90. .spaceshipId));
  91. tree.update(startRec, 1);
  92. }
  93. }
  94. Collections.sort(result, new Comparator<Score>() {
  95. @Override
  96. public int compare(Score s1, Score s2) {
  97. if (s1.score == s2.score) {
  98. return s1.spaceshipId < s2.spaceshipId ? -1 : 1;
  99. } else {
  100. return s1.score < s2.score ? -1 : 1;
  101. }
  102. }
  103. });
  104. for (Score s : result) {
  105. System.out.print(s.spaceshipId + " " + s.score);
  106. }
  107. }
  108. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement