Advertisement
Josif_tepe

Untitled

Oct 17th, 2023
868
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.70 KB | None | 0 0
  1. #include <iostream>
  2. #include <set>
  3. #include <map>
  4. #include <algorithm>
  5. #include <vector>
  6. using namespace std;
  7. const long long max_statues = 1e5 + 10;
  8. const long long max_rect = 3e4 + 10;
  9. const long long max_segment_tree = 130001;
  10. struct statue {
  11.     long long x, y, v;
  12.     statue() {}
  13.     statue(long long _x, long long _y, long long _v) {
  14.         x = _x;
  15.         y = _y;
  16.         v = _v;
  17.     }
  18. };
  19.  
  20. struct rect {
  21.     long long x1, x2, y1, y2;
  22.     rect () {}
  23.     rect(long long _x1, long long _y1, long long _x2, long long _y2) {
  24.         x1 = _x1;
  25.         x2 = _x2;
  26.         y1 = _y1;
  27.         y2 = _y2;
  28.     }
  29. };
  30. struct event {
  31.     long long type; // statues, left edge of  rect, right edge of rect
  32.     long long x, y, v;
  33.     long long y1, y2;
  34.     long long at;
  35.     event() {}
  36.     event(long long _type, long long _x, long long _y, long long _v, long long _y1, long long _y2, long long _at) {
  37.         type = _type;
  38.         x = _x;
  39.         y = _y;
  40.         v = _v;
  41.         y1 = _y1;
  42.         y2 = _y2;
  43.         at = _at;
  44.     }
  45.     bool operator < (const event &tmp) const {
  46.         if(x == tmp.x) {
  47.             return type < tmp.type;
  48.         }
  49.         return x < tmp.x;
  50.     }
  51. };
  52. statue statues[max_statues];
  53. rect rects[max_rect];
  54. long long n, k;
  55. void compress_vertically() {
  56.     set<long long> st;
  57.     for(long long i = 0; i < n; i++) {
  58.         st.insert(statues[i].y);
  59.     }
  60.     for(long long i = 0; i < k; i++) {
  61.         st.insert(rects[i].y1);
  62.         st.insert(rects[i].y2);
  63.     }
  64.     long long value = 0;
  65.     map<long long, long long> compressed_values;
  66.    
  67.     for(long long x : st) {
  68.         if(compressed_values.find(x) == compressed_values.end()) {
  69.             compressed_values[x] = value;
  70.             value++;
  71.         }
  72.     }
  73.    
  74.     for(long long i = 0; i < n; i++) {
  75.         statues[i].y = compressed_values[statues[i].y];
  76.     }
  77.     for(long long i = 0; i < k; i++) {
  78.         rects[i].y1 = compressed_values[rects[i].y1];
  79.         rects[i].y2 = compressed_values[rects[i].y2];
  80.     }
  81.    
  82. }
  83. long long segment_tree[max_segment_tree * 3];
  84. void build(long long L, long long R, long long node) {
  85.     if(L == R) {
  86.         segment_tree[node] = 0;
  87.     }
  88.     else {
  89.         long long mid = (L + R) / 2;
  90.         build(L, mid, 2 * node);
  91.         build(mid + 1, R, 2 * node + 1);
  92.         segment_tree[node] = segment_tree[2 * node] + segment_tree[2 * node + 1];
  93.     }
  94. }
  95. void update(long long L, long long R, long long node, long long idx, long long value) {
  96.     if(L == R) {
  97.         segment_tree[node] += value;
  98.         return;
  99.     }
  100.     long long mid = (L + R) / 2;
  101.     if(idx <= mid) {
  102.         update(L, mid, 2 * node, idx, value);
  103.     }
  104.     else {
  105.         update(mid + 1, R, 2 * node + 1, idx, value);
  106.     }
  107.     segment_tree[node] = segment_tree[2 * node] + segment_tree[2 * node + 1];
  108. }
  109. long long query(long long i, long long j, long long L, long long R, long long node) {
  110.     // L R i L R j L R
  111.     if(i <= L and R <= j) {
  112.         return segment_tree[node];
  113.     }
  114.     if(R < i or j < L){
  115.         return 0;
  116.     }
  117.     long long mid = (L + R) / 2;
  118.     return query(i, j, L, mid, 2 * node) + query(i, j, mid + 1, R, 2 * node + 1);
  119. }
  120. long long sum_till_left_edge[max_statues];
  121. long long result[max_statues];
  122. int main() {
  123.     ios_base::sync_with_stdio(false);
  124.     cin >> n;
  125.     for(long long i = 0; i < n; i++) {
  126.         cin >> statues[i].x >> statues[i].y >> statues[i].v;
  127.     }
  128.    
  129.     cin >> k;
  130.     for(long long i = 0; i < k; i++) {
  131.         cin >> rects[i].x1 >> rects[i].y1 >> rects[i].x2 >> rects[i].y2;
  132.     }
  133.    
  134.     compress_vertically();
  135.     vector<event> queries;
  136.     for(long long i = 0; i < n; i++) {
  137.         event e(1, statues[i].x, statues[i].y, statues[i].v, 0, 0, i);
  138.         queries.push_back(e);
  139.     }
  140.     for(long long i = 0; i < k; i++) {
  141.         event l(0, rects[i].x1, 0, 0, rects[i].y1, rects[i].y2, i);
  142.         event r(2, rects[i].x2, 0, 0, rects[i].y1, rects[i].y2, i);
  143.         queries.push_back(l);
  144.         queries.push_back(r);
  145.     }
  146.     sort(queries.begin(), queries.end());
  147.     build(0, max_segment_tree, 1);
  148.     for(long long i = 0; i < (long long) queries.size(); i++) {
  149.         if(queries[i].type == 1) {
  150.             update(0, max_segment_tree, 1, queries[i].y, queries[i].v);
  151.         }
  152.          if(queries[i].type == 0) {
  153.             sum_till_left_edge[queries[i].at] = query(queries[i].y1, queries[i].y2, 0, max_segment_tree, 1);
  154.         }
  155.         if(queries[i].type == 2) {
  156.             result[queries[i].at] = query(queries[i].y1, queries[i].y2, 0, max_segment_tree, 1) - sum_till_left_edge[queries[i].at];
  157.         }
  158.     }
  159.     for(long long i = 0; i < k; i++) {
  160.         cout << result[i] << "\n";
  161.     }
  162.     return 0;
  163. }
  164.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement