Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <queue>
- #include <iostream>
- #include <vector>
- #include <cstring>
- #include <iostream>
- #include <set>
- #include <cstring>
- #include <stack>
- #include <algorithm>
- #include <map>
- #include <cmath>
- //#include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int maxn = 1e5 + 10;
- const ll INF = 3e16 + 10;
- const int max_point = 10000000;
- int x[maxn], y[maxn], v[maxn];
- vector<int> x_cordinates[max_point];
- vector<pair<int, int> > queries[max_point];
- int y1_query[maxn], y2_query[maxn];
- ll segment_tree[ max_point] = {0};
- void update(int idx, int x) {
- for(; idx <= max_point; idx += idx & -idx) {
- segment_tree[idx] += x;
- }
- }
- ll sum(int i) {
- ll res = 0;
- for(; i >= 1; i -= i & -i)
- {
- res += segment_tree[i];
- }
- return res;
- }
- ll query(int i, int j) {
- return sum(j) - sum(i - 1);
- }
- ll result[maxn];
- int main() {
- ios_base::sync_with_stdio(false);
- int n;
- cin >> n;
- for(int i = 0; i < n; i++) {
- cin >> x[i] >> y[i] >> v[i];
- x[i]++;y[i]++;
- x_cordinates[x[i]].push_back(i);
- }
- int k;
- cin >> k;
- for(int i = 0; i < k; i++) {
- int x1, x2;
- cin >> x1 >> y1_query[i] >> x2 >> y2_query[i];
- x1++;
- x2++;
- y1_query[i]++;
- y2_query[i]++;
- queries[x1 - 1].push_back(make_pair(i, 0));
- queries[x2].push_back(make_pair(i, 1));
- }
- for(int X = 0; X < max_point; X++) {
- for(int i = 0; i < x_cordinates[X].size(); i++) {
- int cord = x_cordinates[X][i];
- update(y[cord], v[cord]);
- }
- for(int i = 0; i < (int)queries[X].size(); i++) {
- pair<int, int> tmp = queries[X][i];
- if(tmp.second == 0) {
- result[tmp.first] -= query( y1_query[tmp.first],y2_query[tmp.first]);
- }
- else {
- result[tmp.first] += query( y1_query[tmp.first], y2_query[tmp.first]);
- }
- }
- }
- for(int i = 0; i < k; i++) {
- cout << result[i] << endl ;
- }
- return 0;
- }
- /*
- 1: 10, 40
- 3: 20
- **/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement