#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;
const int MAX = 1e5 + 5;
const int TREE_SIZE = MAX * 17;
const int MAXVAL = (1 << 17) - 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];
}
SegTree2D tree;
pii scores[MAX];
array<int, 4> querries[MAX];
int ans[MAX];
int main(){
int n, q; cin >> n >> q;
for (int i = 0; i < n; i++)
{
scanf("%d %d", &scores[i].first, &scores[i].second);
tree.update(0, 0, MAXVAL, scores[i].first, scores[i].second, 1);
}
sort(scores, scores + n, comp1);
for (int i = 0; i < q; i++)
{
scanf("%d%d%d", &querries[i][0], &querries[i][1], &querries[i][2]);
querries[i][3] = i;
}
sort(querries, querries + q, comp2);
int last = 0;
for (int i = 0; i < q; i++)
{
while(last < n && scores[last].first + scores[last].second < querries[i][2]){
tree.update(0, 0, MAXVAL, scores[last].first, scores[last].second, -1);
last++;
}
ans[querries[i][3]] = n - last;
if(querries[i][0] != 0){
ans[querries[i][3]] -= tree.ask(0, 0, MAXVAL, 0, querries[i][0] - 1, 0, MAXVAL);
}
if(querries[i][1] != 0){
ans[querries[i][3]] -= tree.ask(0, 0, MAXVAL, 0, MAXVAL, 0, querries[i][1] - 1);
}
if(querries[i][1] != 0 && querries[i][0] != 0){
ans[querries[i][3]] += 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';
}
}
Compilation message
examination.cpp: In function 'int main()':
examination.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
109 | scanf("%d %d", &scores[i].first, &scores[i].second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:115:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
115 | scanf("%d%d%d", &querries[i][0], &querries[i][1], &querries[i][2]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
263 ms |
306460 KB |
Output is correct |
| 2 |
Correct |
289 ms |
306356 KB |
Output is correct |
| 3 |
Correct |
259 ms |
306356 KB |
Output is correct |
| 4 |
Incorrect |
264 ms |
306272 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2645 ms |
577364 KB |
Output is correct |
| 2 |
Correct |
2527 ms |
579600 KB |
Output is correct |
| 3 |
Correct |
2290 ms |
579868 KB |
Output is correct |
| 4 |
Correct |
1356 ms |
359736 KB |
Output is correct |
| 5 |
Correct |
966 ms |
366964 KB |
Output is correct |
| 6 |
Correct |
505 ms |
310680 KB |
Output is correct |
| 7 |
Correct |
2168 ms |
579680 KB |
Output is correct |
| 8 |
Correct |
2040 ms |
579808 KB |
Output is correct |
| 9 |
Correct |
1989 ms |
579800 KB |
Output is correct |
| 10 |
Correct |
887 ms |
362452 KB |
Output is correct |
| 11 |
Correct |
1354 ms |
345500 KB |
Output is correct |
| 12 |
Correct |
495 ms |
310280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2645 ms |
577364 KB |
Output is correct |
| 2 |
Correct |
2527 ms |
579600 KB |
Output is correct |
| 3 |
Correct |
2290 ms |
579868 KB |
Output is correct |
| 4 |
Correct |
1356 ms |
359736 KB |
Output is correct |
| 5 |
Correct |
966 ms |
366964 KB |
Output is correct |
| 6 |
Correct |
505 ms |
310680 KB |
Output is correct |
| 7 |
Correct |
2168 ms |
579680 KB |
Output is correct |
| 8 |
Correct |
2040 ms |
579808 KB |
Output is correct |
| 9 |
Correct |
1989 ms |
579800 KB |
Output is correct |
| 10 |
Correct |
887 ms |
362452 KB |
Output is correct |
| 11 |
Correct |
1354 ms |
345500 KB |
Output is correct |
| 12 |
Correct |
495 ms |
310280 KB |
Output is correct |
| 13 |
Execution timed out |
3097 ms |
579740 KB |
Time limit exceeded |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
263 ms |
306460 KB |
Output is correct |
| 2 |
Correct |
289 ms |
306356 KB |
Output is correct |
| 3 |
Correct |
259 ms |
306356 KB |
Output is correct |
| 4 |
Incorrect |
264 ms |
306272 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
