Advertisement
Josif_tepe

Untitled

Oct 5th, 2023
767
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.37 KB | None | 0 0
  1. #include <queue>
  2. #include <iostream>
  3. #include <vector>
  4. #include <cstring>
  5. #include <iostream>
  6. #include <set>
  7. #include <cstring>
  8. #include <stack>
  9. #include <algorithm>
  10. #include <map>
  11. #include <cmath>
  12. //#include <bits/stdc++.h>
  13. using namespace std;
  14. typedef long long ll;
  15. const int maxn = 1e5 + 10;
  16. const ll INF = 3e16 + 10;
  17. const int max_point = 10000000;
  18. int x[maxn], y[maxn], v[maxn];
  19. vector<int> x_cordinates[max_point];
  20. vector<pair<int, int> > queries[max_point];
  21. int y1_query[maxn], y2_query[maxn];
  22. ll segment_tree[ max_point] = {0};
  23. void update(int idx, int x) {
  24.     for(; idx <= max_point; idx += idx & -idx) {
  25.         segment_tree[idx] += x;
  26.     }
  27. }
  28. ll sum(int i) {
  29.     ll res = 0;
  30.     for(; i >= 1; i -= i & -i)
  31.     {
  32.         res += segment_tree[i];
  33.     }
  34.     return res;
  35. }
  36. ll query(int i, int j) {
  37.     return sum(j) - sum(i - 1);
  38. }
  39. ll result[maxn];
  40. int main() {
  41.     ios_base::sync_with_stdio(false);
  42.     int n;
  43.     cin >> n;
  44.     for(int i = 0; i < n; i++) {
  45.         cin >> x[i] >> y[i] >> v[i];
  46. x[i]++;y[i]++;
  47.         x_cordinates[x[i]].push_back(i);
  48.     }
  49.     int k;
  50.     cin >> k;
  51.     for(int i = 0; i < k; i++) {
  52.         int x1, x2;
  53.         cin >> x1 >> y1_query[i] >> x2 >> y2_query[i];
  54.         x1++;
  55.         x2++;
  56.         y1_query[i]++;
  57.         y2_query[i]++;
  58.        
  59.         queries[x1 - 1].push_back(make_pair(i, 0));
  60.         queries[x2].push_back(make_pair(i, 1));
  61.     }
  62.    
  63.     for(int X = 0; X < max_point; X++) {
  64.         for(int i = 0; i < x_cordinates[X].size(); i++) {
  65.             int cord = x_cordinates[X][i];
  66.             update(y[cord], v[cord]);
  67.         }
  68.        
  69.         for(int i = 0; i < (int)queries[X].size(); i++) {
  70.             pair<int, int> tmp = queries[X][i];
  71.             if(tmp.second == 0) {
  72.                 result[tmp.first] -= query( y1_query[tmp.first],y2_query[tmp.first]);
  73.             }
  74.             else {
  75.                 result[tmp.first] += query( y1_query[tmp.first], y2_query[tmp.first]);
  76.             }
  77.                                              
  78.                                                    
  79.         }
  80.     }
  81.    
  82.    
  83.                  for(int i = 0; i < k; i++) {
  84.                                                                   cout << result[i] << endl      ;
  85.                                                                   }
  86.     return 0;
  87. }
  88. /*
  89.  1: 10, 40
  90.  3: 20
  91.  
  92.  
  93.  **/
  94.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement