Advertisement
Guest User

Untitled

a guest
Apr 22nd, 2018
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.30 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4.  
  5. #include <fstream>
  6.  
  7.  
  8. using namespace std;
  9.  
  10.  
  11. struct node{
  12.  
  13. int value;
  14. int set_val;
  15. };
  16.  
  17. vector<node> build ( int wall_l, int& x){
  18.  
  19. x = 1;
  20. while (x <= wall_l)
  21. x <<= 1;
  22.  
  23. vector<node> tree(2*x);
  24. for(int i = 0; i < 2*x; i++) {
  25. tree[i].value = 0;
  26. tree[i].set_val = 100000000 + 1;
  27. }
  28. for(int i = 0; i < wall_l; i++)
  29. tree[x + i - 1].value = 0;
  30.  
  31.  
  32.  
  33. for(int i = x - 2; i >= 0; i--)
  34. tree[i].value = min(tree[2*i + 1].value,tree[2*i +2].value);
  35.  
  36. return tree;
  37. }
  38.  
  39. void push (int v , int tl, int tr, vector<node>& tree){
  40.  
  41. if(tree[v].set_val != 100000000 + 1 ){
  42. tree[v].value = tree[v].set_val;
  43. if( tl != tr){
  44. tree[2*v + 1].set_val = tree[v].set_val;
  45. tree[2*v + 2].set_val = tree[v].set_val;
  46. }
  47. tree[v].set_val = 100000000 + 1;
  48. }
  49.  
  50. }
  51.  
  52. void ragemod(int v, int tl, int tr, int l, int r,
  53. int set,vector<node>& tree){
  54. push(v,tl,tr,tree);
  55. if(l > tr || r < tl ){
  56. return;
  57. }
  58. if(l <= tl && tr <= r){
  59. //if(set != 100000000 + 1){
  60. tree[v].set_val = set;
  61.  
  62. //}
  63. push(v,tl,tr,tree);
  64. return;
  65. }
  66. int tm = (tr + tl)/2;
  67. ragemod(2*v + 1,tl,tm,l,r,set,tree);
  68. ragemod(2*v + 2,tm + 1,tr,l,r,set,tree);
  69. tree[v].value = min(tree[2*v + 1].value,tree[2*v + 2].value);
  70. }
  71.  
  72. vector< int> get_min( int v, int l, int r, int a, int b,vector<node>& tree){
  73.  
  74. push(v,l,r,tree);
  75.  
  76. if (r < a || b < l){
  77. vector< int> res;
  78. res.push_back(100000000 + 1);
  79. res.push_back(v);
  80. res.push_back(l);
  81. res.push_back(r);
  82. return res;
  83. }
  84. if (l >= a && r <= b){
  85. vector< int> res;
  86. res.push_back(tree[v].value);
  87. res.push_back(v);
  88. res.push_back(l);
  89. res.push_back(r);
  90. return res;
  91. }
  92. int m = (l + r) / 2;
  93. vector< int> res;
  94. vector< int> res1 = get_min( 2 * v + 1, l, m, a, b,tree);
  95. vector< int> res2 = get_min(2 * v + 2, m + 1, r, a, b,tree);
  96.  
  97. if(res1[0] <= res2[0]){
  98. res.push_back(res1[0]);
  99. res.push_back(res1[1]);
  100. res.push_back(res1[2]);
  101. res.push_back(res1[3]);
  102. }
  103. else if (res1[0] > res2[0]){
  104. res.push_back(res2[0]);
  105. res.push_back(res2[1]);
  106. res.push_back(res2[2]);
  107. res.push_back(res2[3]);
  108. }
  109. return res;
  110. }
  111.  
  112. int search_index(int v, int tl, int tr, vector<node>& tree,int x ){
  113. if( v < x - 1) {
  114. int tm = (tl + tr) / 2;
  115. push(2 * v + 1, tl, tm, tree);
  116. push(2 * v + 2, tm + 1,tr,tree);
  117. if (tree[2 * v + 1].value == tree[v].value) {
  118.  
  119. return search_index( 2 * v + 1, tl, tm, tree,x);
  120.  
  121. }
  122. else if (tree[2 * v + 2].value == tree[v].value) {
  123. return search_index( 2 * v + 2, tm + 1, tr, tree,x);
  124. }
  125. }
  126. else {
  127. return v;
  128. }
  129. }
  130.  
  131. int main() {
  132.  
  133. ifstream in("chinatown.in");
  134.  
  135. int length_wall, op_count;
  136. cin >> length_wall >> op_count;
  137.  
  138. int x = 1;
  139. vector<node> tree = build(length_wall,x);
  140.  
  141. cout << endl;
  142. for (int i = 0; i < op_count ; i++){
  143. string op_type;
  144. cin >> op_type;
  145. if(op_type == "defend"){
  146. int a, b, c;
  147. cin >> a >> b >> c;
  148. ragemod(0,0,x - 1,a - 1,b - 1,c,tree);
  149. }
  150. else if (op_type == "attack"){
  151. int a, b;
  152. cin >> a >> b;
  153. vector< int> result = get_min(0,0,x - 1,a - 1,b - 1,tree);
  154. cout << result[0] << " " << search_index(result[1],result[2],result[3],tree,x) - x + 2<<endl;
  155.  
  156. }
  157. }
  158.  
  159.  
  160. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement