Advertisement
Guest User

Untitled

a guest
Mar 24th, 2019
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.74 KB | None | 0 0
  1. #include <vector>
  2. #include <iostream>
  3. using namespace std;
  4.  
  5. long long MAX_VALUE = INT32_MAX + 1;
  6.  
  7. struct node {
  8. long long value;
  9. long long tr_max = -MAX_VALUE;
  10.  
  11. node(long long m) {
  12. value = m;
  13. }
  14. };
  15.  
  16. typedef node *link;
  17.  
  18. struct check {
  19. int left;
  20. int right;
  21. long long value;
  22.  
  23. check(int l, int r, long long v) {
  24. left = l;
  25. right = r;
  26. value = v;
  27. }
  28. };
  29.  
  30. typedef check *check_1;
  31.  
  32. vector<link> tree;
  33. vector<check_1> check_tree;
  34.  
  35.  
  36. void push(int v, int left, int right) {
  37. if (tree[v]->tr_max != -MAX_VALUE)
  38. tree[v]->value = tree[v]->tr_max;
  39. if (left != right) {
  40. tree[v * 2 + 1]->tr_max = max(tree[v * 2 + 1]->tr_max, tree[v]->tr_max);
  41. tree[v * 2 + 2]->tr_max = max(tree[v * 2 + 2]->tr_max, tree[v]->tr_max);
  42. int middle = left - (left - right) / 2;
  43. push(2 * v + 1, left, middle);
  44. push(2 * v + 2, middle + 1, right);
  45. tree[v]->value = min(tree[v * 2 + 1]->value, tree[v * 2 + 2]->value);
  46. }
  47. }
  48.  
  49. long long getMinValue(int a, int b, int left, int right, int v) {
  50. if (left > b || right < a) {
  51. return MAX_VALUE;
  52. }
  53. if (left >= a && right <= b) {
  54. return tree[v]->value;
  55. }
  56. long long new_left = getMinValue(a, b, left, left - (left - right) / 2, v * 2 + 1);
  57. long long new_right = getMinValue(a, b, left - (left - right) / 2 + 1, right, v * 2 + 2);
  58. return min(new_left, new_right);
  59. }
  60.  
  61. void set(int a, int b, long long x, int v, int left, int right) {
  62. if (left > b || right < a)
  63. return;
  64. if (left >= a && right <= b) {
  65. tree[v]->tr_max = max(tree[v]->tr_max, x);
  66. return;
  67. }
  68. int vm = left - (left - right) / 2;
  69. set(a, b, x, v * 2 + 1, left, vm);
  70. set(a, b, x, v * 2 + 2, vm + 1, right);
  71. }
  72.  
  73. int main() {
  74. int n, m, x = 1;
  75. cin >> n >> m;
  76. while (x < n) {
  77. x <<= 1;
  78. }
  79. tree.resize(x * 2 - 1);
  80. check_tree.resize(m);
  81. for (auto &i : tree) {
  82. i = new node(MAX_VALUE);
  83. }
  84.  
  85. int l, r, j = 0;
  86. long long v;
  87. while (cin >> l) {
  88. cin >> r >> v;
  89. check_tree[j++] = new check(l - 1, r - 1, v);
  90. set(l - 1, r - 1, v, 0, 0, x - 1);
  91. }
  92.  
  93. push(0, 0, x - 1);
  94. for (int i = 0; i < m; i++) {
  95. if (getMinValue(check_tree[i]->left, check_tree[i]->right, 0, x - 1, 0)
  96. != check_tree[i]->value) {
  97. cout << "inconsistent";
  98. return 0;
  99. }
  100. }
  101. cout << "consistent\n";
  102. for (int i = x - 1; i < x - 1 + n; i++) {
  103. if (tree[i]->value == MAX_VALUE) {
  104. cout << (1ll << 31) - 1 << " ";
  105. continue;
  106. }
  107. cout << tree[i]->value << " ";
  108. }
  109. return 0;
  110. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement