#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;
const int TREE_SIZE = 30 * 1e5;
const int MAXVAL = (1 << 30) - 1;
struct SegTree1D{
vector<int> tree, L, R;
int nxt = 0;
SegTree1D(){
addNode();
}
int addNode(){
tree.emplace_back(0);
L.emplace_back(0);
R.emplace_back(0);
return nxt++;
}
void update(int node, int l, int r, int pos, int val){
tree[node] += val;
if(l == r) return;
int mid = (l + r) / 2;
if(pos <= mid){
if(!L[node]) L[node] = addNode();
update(L[node], l, mid, pos, val);
}
else{
if(!R[node]) R[node] = addNode();
update(R[node], mid + 1, r, pos, val);
}
}
int ask(int node, int l, int r, int ql, int qr){
if(r < ql || qr < l) return 0;
if(ql <= l && r <= qr) return tree[node];
int ans = 0;
int mid = (l + r) / 2;
if(L[node]) ans += ask(L[node], l, mid, ql, qr);
if(R[node]) ans += ask(R[node], mid + 1, r, ql, qr);
return ans;
}
};
struct SegTree2D{
SegTree1D tree[TREE_SIZE];
int L[TREE_SIZE], R[TREE_SIZE];
int nxt = 0;
int addNode(){
return nxt++;
}
SegTree2D(){
addNode();
memset(L, 0, sizeof(L));
memset(R, 0, sizeof(R));
}
void update(int node, int l, int r, int ux, int uy, int val){
tree[node].update(0, 0, MAXVAL, ux, val);
if(l == r) return;
int mid = (l + r) / 2;
if(uy <= mid){
if(!L[node]) L[node] = addNode();
update(L[node], l, mid, ux, uy, val);
}
else{
if(!R[node]) R[node] = addNode();
update(R[node], mid + 1, r, ux, uy, val);
}
}
int ask(int node, int l, int r, int x1, int x2, int y1, int y2){
if(r < y1 || y2 < l) return 0;
if(y1 <= l && r <= y2) return tree[node].ask(0, 0, MAXVAL, x1, x2);
int ans = 0;
int mid = (l + r) / 2;
if(L[node]) ans += ask(L[node], l, mid, x1, x2, y1, y2);
if(R[node]) ans += ask(R[node], mid + 1, r, x1, x2, y1, y2);
return ans;
}
};
bool comp1(pii p1, pii p2){
return (p1.first + p1.second) < (p2.first + p2.second);
}
bool comp2(array<int, 4>& a1, array<int, 4>& a2){
return a1[2] < a2[2];
}
int main(){
SegTree2D tree;
int n, q; cin >> n >> q;
vector<pii> scores(n);
for (int i = 0; i < n; i++)
{
cin >> scores[i].first >> scores[i].second;
tree.update(0, 0, MAXVAL, scores[i].first, scores[i].second, 1);
}
sort(scores.begin(), scores.end(), comp1);
vector<array<int, 4>> querries(q);
for (int i = 0; i < q; i++)
{
cin >> querries[i][0] >> querries[i][1] >> querries[i][2];
querries[i][3] = i;
}
sort(querries.begin(), querries.end(), comp2);
int ans[q];
int last = 0;
for (int i = 0; i < q; i++)
{
int l = 0, r = n - 1;
int low = 0;
while(l <= r){
int mid = (l + r) / 2;
if(scores[mid].first + scores[mid].second < querries[i][2]){
l = mid + 1;
low = mid + 1;
}
else{
r = mid - 1;
}
}
while(last < low){
tree.update(0, 0, MAXVAL, scores[last].first, scores[last].second, -1);
last++;
}
ans[querries[i][3]] = n - last -
(tree.ask(0, 0, MAXVAL, 0, querries[i][0] - 1, 0, MAXVAL) +
tree.ask(0, 0, MAXVAL, 0, MAXVAL, 0, querries[i][1] - 1) -
tree.ask(0, 0, MAXVAL, 0, querries[i][0] - 1, 0, querries[i][1] - 1));
}
for (int i = 0; i < q; i++)
{
cout << ans[i] << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1047 ms |
975192 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
946 ms |
1000504 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
946 ms |
1000504 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1047 ms |
975192 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
