#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
struct point{
ll x, y, z, id;
};
struct normalize{
vector<ll> poi, pot;
void add(ll x){
poi.push_back(x);
}
void start(){
sort(poi.begin(), poi.end());
pot.push_back(poi[0]);
for(int i = 1; i < (int)poi.size(); i++){
if(poi[i] != poi[i-1]){
pot.push_back(poi[i]);
}
}
}
int encode(ll x){
return lower_bound(pot.begin(), pot.end(), x) - pot.begin()+1;
}
};
struct Fenwick2D {
int n, m;
vector<vector<int>> bit;
vector<vector<int>> f;
Fenwick2D(int n, int m) : n(n), m(m), bit(n + 1), f(n + 1) {}
void fakeAdd(int i0, int j0) {
for (int i = i0; i <= n; i += i & -i) {
for (int j = j0; j <= m; j += j & -j) {
f[i].push_back(j);
}
}
}
void work() {
for (int i = 1; i <= n; i++) {
f[i].push_back(0);
sort(f[i].begin(), f[i].end());
f[i].resize(unique(f[i].begin(), f[i].end()) - f[i].begin());
bit[i].resize(f[i].size(), 0);
}
}
void add(int i0, int j0, int x) {
for (int i = i0; i <= n; i += i & -i) {
for (int j = lower_bound(f[i].begin(), f[i].end(), j0) - f[i].begin(); j < (int)f[i].size(); j += j & -j) {
bit[i][j] += x;
}
}
}
int sum(int i0, int j0) {
int res = 0;
for (int i = i0; i > 0; i -= i & -i) {
for (int j = upper_bound(f[i].begin(), f[i].end(), j0) - f[i].begin() - 1; j > 0; j -= j & -j) {
res += bit[i][j];
}
}
return res;
}
};
void solve(){
int n, Q;
cin >> n >> Q;
vector<point> a(n+1);
for(int i = 1; i <= n; i++){
cin >> a[i].x >> a[i].y;
a[i].z = a[i].x+a[i].y;
}
vector<point> q(Q+1);
for(int i = 1; i <= Q; i++){
cin >> q[i].x >> q[i].y >> q[i].z;
q[i].id = i;
}
normalize norm;
for(int i = 1; i <= n; i++){
norm.add(a[i].x);
norm.add(a[i].y);
}
for(int i = 1; i <= Q; i++){
norm.add(q[i].x);
norm.add(q[i].y);
}
norm.start();
int N = norm.pot.size();
for(int i = 1; i <= n; i++){
a[i].x = N-norm.encode(a[i].x);
a[i].y = N-norm.encode(a[i].y);
}
for(int i = 1; i <= Q; i++){
q[i].x = N-norm.encode(q[i].x);
q[i].y = N-norm.encode(q[i].y);
}
Fenwick2D bit(N+1, N+1);
for(int i = 1; i <= n; i++){
bit.fakeAdd(a[i].x, a[i].y);
}
bit.work();
sort(a.begin()+1, a.end(), [&](point a, point b){return a.z > b.z;});
sort(q.begin()+1, q.end(), [&](point a, point b){return a.z > b.z;});
vector<ll> ans(Q+1);
int j = 1;
for(int i = 1; i <= Q; i++){
while(j <= n && a[j].z >= q[i].z){
bit.add(a[j].x, a[j].y, 1);
j++;
}
ans[q[i].id] = bit.sum(q[i].x, q[i].y);
}
for(int i = 1; i <= Q; i++){
cout << ans[i] << "\n";
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
741 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
902 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
902 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
741 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
