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
| #include<bits/stdc++.h> using namespace std;
typedef pair<int,int> pii;
const int N=3e5+5;
int n,m; int x,c; int l,r; int a[N],s[N];
vector<int> locs; vector<pii> add,ask;
int bfind(int num){ return lower_bound(locs.begin(),locs.end(),num)-locs.begin()+1; }
void dis(){ sort(locs.begin(),locs.end()); locs.erase(unique(locs.begin(),locs.end()),locs.end()); for(auto item:add){ x=bfind(item.first); c=item.second; a[x]+=c; } }
int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d%d",&x,&c); add.push_back({x,c}); locs.push_back(x); } for(int i=1;i<=m;i++){ scanf("%d%d",&l,&r); ask.push_back({l,r}); locs.push_back(l); locs.push_back(r); } dis(); for(int i=1;i<locs.size()+1;i++){ s[i]=s[i-1]+a[i]; } for(auto item:ask){ l=bfind(item.first); r=bfind(item.second); printf("%d\n",s[r]-s[l-1]); } return 0; }
|