#include <bits/stdc++.h>
using namespace std;
class segmenttree{
private:
vector<int> vect;
int sze;
void privupdate(int segpos, int segleft, int segright, int arrpos, int val){
if(segleft!=segright){
int segmid = (segleft+segright)/2;
if(arrpos<=segmid){
privupdate(2*segpos+1, segleft, segmid, arrpos, val);
}
else{
privupdate(2*segpos+2, segmid+1, segright, arrpos, val);
}
vect[segpos]=vect[2*segpos+1]+vect[2*segpos+2];
}
else{
vect[segpos]+=val;
}
}
int privquery(int segpos, int segleft, int segright, int arrleft, int arrright){
if(arrleft==segleft && arrright==segright){
return vect[segpos];
}
else{
int segmid = (segleft+segright)/2;
if(arrright<=segmid){
return privquery(2*segpos+1, segleft, segmid, arrleft, arrright);
}
else if(arrleft>segmid){
return privquery(2*segpos+2, segmid+1, segright, arrleft, arrright);
}
else{
return privquery(2*segpos+1, segleft, segmid, arrleft, segmid)+privquery(2*segpos+2, segmid+1, segright, segmid+1, arrright);
}
}
}
public:
segmenttree(int _sze):sze(_sze){
vect.resize(4*sze+5, 0);
}
int query(int left, int right){
return privquery(0, 0, sze-1, left, right);
}
void update(int pos, int val){
privupdate(0, 0, sze-1, pos, val);
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
cin >> n >> q;
pair<int, pair<int, int> > arr[n];
segmenttree one(n);
segmenttree two(n);
vector<pair<int, int> > arr11(n);
vector<pair<int, int> > arr12(n);
vector<pair<int, int> > arr21(n);
vector<pair<int, int> > arr22(n);
for(int i=0; i<n; i++){
cin >> arr[i].second.first >> arr[i].second.second;
arr[i].first = arr[i].second.first+arr[i].second.second;
one.update(i, 1);
two.update(i, 1);
}
sort(arr, arr+n);
for(int i=0; i<n; i++){
arr11[i].first = arr[i].second.first;
arr21[i].first = arr[i].second.second;
arr12[i].first = arr[i].second.first;
arr12[i].second = i;
arr22[i].first = arr[i].second.second;
arr22[i].second = i;
}
sort(arr12.begin(), arr12.end());
sort(arr22.begin(), arr22.end());
for(int i=0; i<n; i++){
arr11[arr12[i].second].second=i;
arr21[arr22[i].second].second=i;
}
pair<tuple<int, int, int, int>, int> queries[q]; // sum, first, second, pos, ans;
for(int i=0; i<q; i++){
int a, b, c;
cin >> a >> b >> c;
queries[i].first = {max(c, a+b), a, b, i};
}
sort(queries, queries+q);
int posq = 0;
for(int i=0; i<n; i++){
while(posq<q && get<0>(queries[posq].first)<=arr[i].first){
int aa = get<1>(queries[posq].first);
int bb = get<2>(queries[posq].first);
pair<int, int> temp1 = {aa, 0};
pair<int, int> temp2 = {bb, 0};
int a = lower_bound(arr12.begin(), arr12.end(), temp1)-arr12.begin();
int b = lower_bound(arr22.begin(), arr22.end(), temp2)-arr22.begin();
int c = one.query(min(a, n-1), n-1);
int d = two.query(min(b, n-1), n-1);
int e = n-i;
queries[posq].second = c+d-e;
posq++;
}
one.update(arr11[i].second, -1);
two.update(arr21[i].second, -1);
}
int ans[q];
for(int i=0; i<q; i++){
ans[get<3>(queries[i].first)]=queries[i].second;
}
for(int i=0; i<q; i++){
cout << ans[i] << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
320 KB |
Output is correct |
| 5 |
Correct |
1 ms |
324 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
224 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
190 ms |
10996 KB |
Output is correct |
| 2 |
Incorrect |
174 ms |
11080 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
190 ms |
10996 KB |
Output is correct |
| 2 |
Incorrect |
174 ms |
11080 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
320 KB |
Output is correct |
| 5 |
Correct |
1 ms |
324 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
224 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
