1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
| #include <bits/stdc++.h> using namespace std; const int N = 3e5+10; int a[N] = {0},s[N]= {0}; typedef pair<int,int> PA;
vector<int> index_arr; vector<PA> conderation_arr; vector<PA> query_arr;
int find(int x) { int l = 0,r = index_arr.size() - 1; while( l < r) { int mid = (l + r) / 2; if(index_arr[mid] >= x ) { r = mid; } else { l = mid + 1; } } return r + 1; }
int main() { int n,m; cin >> n >> m; for(int i = 0; i < n;++i) { int x,c; cin >> x >> c; conderation_arr.push_back({x,c}); index_arr.push_back(x); } for(int i = 0; i < m;++i) { int l,r; cin >> l >> r; query_arr.push_back({l,r}); index_arr.push_back(l); index_arr.push_back(r); } sort(index_arr.begin(),index_arr.end()); index_arr.erase(unique(index_arr.begin(),index_arr.end()),index_arr.end()); for( auto item : conderation_arr) { int x = find(item.first); a[x] += item.second; } for(int i = 1; i <= index_arr.size(); ++i) { s[i] = s[i-1] + a[i]; } for(auto item: query_arr) { int l = find(item.first); int r = find(item.second); int num = s[r] - s[l - 1]; cout << num << endl; } return 0; }
|