#include <bits/stdc++.h>
// #define int long long
#define ll long long
#define pb push_back
using namespace std;
struct point{
int a, b, c, id, val;
};
vector<point> student;
const int maxn = 1e5 + 10;
int ans[maxn];
bool cmp(point x, point y){
if(x.a != y.a) return x.a > y.a;
if(x.b != y.b) return x.b < y.b;
return x.c < y.c;
}
void inv(point &a){
a.a = -a.a;
a.b = -a.b;
a.c = -a.c;
}
int bit[2*maxn];
int getsum(int i){
ll sum = 0;
while(i > 0){
sum+=bit[i];
i-=(i & (-i));
}
return sum;
}
void update(int i, int v){
while(i < 2*maxn){
bit[i]+=v;
i+=(i & (-i));
}
}
void dnc(int l, int r){
if(l + 1 == r) return;
int mid = (l + r)/2;
dnc(l , mid); dnc(mid, r);
vector<pair<int,int>> rec; vector<point> tmp;
int a = l, b = mid, sum = 0;
while(a < mid && b < r) {
if(student[a].b > student[b].b){
update(student[a].c, student[a].val);
sum+=student[a].val;
rec.push_back({student[a].c,student[a].val});
tmp.push_back(student[a++]);
}
else{
ans[student[b].id] += sum - getsum(student[b].c);
tmp.push_back(student[b++]);
}
}
while(a < mid) tmp.push_back(student[a++]);
while(b < r) ans[student[b].id] += sum - getsum(student[b].c), tmp.push_back(student[b++]);
for(int i = l ; i < r ; ++i) student[i] = tmp[i - l];
for(auto x: rec) update(x.first, -x.second);
vector<pair<int,int>> ().swap(rec);
vector<point> ().swap(tmp);
}
signed main(){
int n, q;
cin >> n >> q;
vector<int> compress;
compress.pb(-1e18); compress.pb(1e18);
for(int i = 0; i < n; i++){
point tmp; cin >> tmp.a >> tmp.b;
tmp.c = tmp.a + tmp.b; tmp.id = 0; tmp.val = 1;
// inv(tmp);
compress.pb(tmp.a);compress.pb(tmp.b);compress.pb(tmp.c);
student.pb(tmp);
}
int cnt = 1;
int _q = q;
while(q--){
point tmp;
cin >> tmp.a >> tmp.b >> tmp.c;
tmp.a--; tmp.b--; tmp.c--;
tmp.val = 0;
compress.pb(tmp.a); compress.pb(tmp.b); compress.pb(tmp.b);
tmp.id = cnt;
// inv(tmp);
cnt++;
student.pb(tmp);
}
sort(compress.begin(),compress.end());
for(auto &x : student){
x.a = lower_bound(compress.begin(),compress.end(),x.a) - compress.begin();
x.b = lower_bound(compress.begin(),compress.end(),x.b) - compress.begin();
x.c = lower_bound(compress.begin(),compress.end(),x.c) - compress.begin();
}
sort(student.begin(),student.end(), cmp);
dnc(0, n + _q);
for(int i = 1; i <= _q; i++){
cout << ans[i] << "\n";
}
}
Compilation message
examination.cpp: In function 'int main()':
examination.cpp:79:17: warning: overflow in conversion from 'double' to 'std::vector<int>::value_type' {aka 'int'} changes value from '-1.0e+18' to '-2147483648' [-Woverflow]
79 | compress.pb(-1e18); compress.pb(1e18);
| ^~~~~
examination.cpp:79:37: warning: overflow in conversion from 'double' to 'std::vector<int>::value_type' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
79 | compress.pb(-1e18); compress.pb(1e18);
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
213 ms |
16544 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
213 ms |
16544 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
