#include <iostream>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,fma")
using namespace std;
#define f first
#define s second
const int MAXN = 1e5 + 10;
pair <int, int> a[MAXN];
map <int, vector <vector <int> > > q;
unordered_map <int, unordered_map <int, int> > fw;
int ans[MAXN];
void upd(int x, int y, int val) {
for(long long j = x; j <= 2e9; j += j & -j) {
for(long long z = y; z <= 2e9; z += z & -z) {
fw[j][z] += val;
}
}
}
int get(int x, int y) {
int res = 0;
for(int i = x; i > 0; i -= i & -i) {
if(!fw.count(i)) continue;
for(int j = y; j > 0; j -= j & -j) {
if(!fw[i].count(j)) continue;
res += fw[i][j];
}
}
return res;
}
int get(int x1, int y1, int x2, int y2) {
return get(x2, y2) - get(x1 - 1, y2) - get(x2 - 1, y1) + get(x1, y1);
}
int main() {
int n, qq;
cin >> n >> qq;
for(int i = 0; i < n; ++i) cin >> a[i].f >> a[i].s;
sort(a, a + n);
int x, y, z;
for(int i = 0; i < qq; ++i) {
cin >> x >> y >> z;
q[x].push_back({y, z, i});
}
for(int i = 0; i < n; ++i) upd(a[i].s, a[i].f + a[i].s, 1);
int ptr = 0;
for(auto it : q) {
while(ptr < n && a[ptr].f < it.f) {
upd(a[ptr].s, a[ptr].f + a[ptr].s, -1);
++ptr;
}
for(auto j : q[it.f]) ans[j[2]] = get(j[0], j[1], 2e9, 2e9);
}
for(int i = 0; i < qq; ++i) cout << ans[i] << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
292 KB |
Output is correct |
2 |
Correct |
1 ms |
300 KB |
Output is correct |
3 |
Incorrect |
1 ms |
288 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3077 ms |
179528 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3077 ms |
179528 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
292 KB |
Output is correct |
2 |
Correct |
1 ms |
300 KB |
Output is correct |
3 |
Incorrect |
1 ms |
288 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |