#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
struct grades{
int x, y, z;
bool operator < (const grades &aux)const{
if(z != aux.z) return z > aux.z;
if(x != aux.x) return x > aux.x;
return y > aux.y;
}
};
struct teacher{
int x, y, z, p;
bool operator < (const teacher &aux)const{
if(z != aux.z) return z > aux.z;
if(x != aux.x) return x > aux.x;
return y > aux.y;
}
};
grades a[100005];
teacher b[100005];
int ans[100005];
int n, q;
struct node{
int tip, val;
node *arb;
node *left, *right;
node(bool x){
tip = x;
val = 0;
arb = left = right = NULL;
}
};
node *arb;
int y, nx, ny, NR;
void update(int x, node *nod, int st, int dr){
if(st == dr){
if(nod->tip == 1){
if(nod->arb == NULL) nod->arb = new node(0);
update(y, nod->arb, 1, ny);
}
else ++nod->val;
return ;
}
int mij = (st + dr) / 2;
if(x <= mij){
if(nod->left == NULL) nod->left = new node(nod->tip);
update(x, nod->left, st, mij);
}
else{
if(nod->right == NULL) nod->right = new node(nod->tip);
update(x, nod->right, mij + 1, dr);
}
if(nod->tip == 1){
if(nod->arb == NULL) nod->arb = new node(0);
update(y, nod->arb, 1, ny);
}
else{
nod->val = 0;
if(nod->left != NULL) nod->val += nod->left->val;
if(nod->right!= NULL) nod->val += nod->right->val;
}
}
int yr, yl;
int query(int x, int y, node *nod, int st, int dr){
if(x <= st && dr <= y){
if(nod->tip == 1){
if(nod->arb == NULL) return 0;
return query(yl, yr, nod->arb, 1, ny);
}
else return nod->val;
}
int mij = (st + dr) / 2;
int val = 0;
if(x <= mij){
if(nod->left != NULL) val += query(x, y, nod->left, st, mij);
}
if(mij + 1 <= y){
if(nod->right != NULL) val += query(x, y, nod->right, mij + 1, dr);
}
return val;
}
set <int> sx, sy;
map <int, int> fx, fy;
int main()
{
scanf("%d%d", &n, &q);
for(int i = 1; i <= n ; ++i){
scanf("%d%d", &a[i].x, &a[i].y);
a[i].z = a[i].x + a[i].y;
sx.insert(a[i].x); sy.insert(a[i].y);
}
for(int i = 1; i <= q ; ++i){
scanf("%d%d%d", &b[i].x, &b[i].y, &b[i].z), b[i].p = i;
sx.insert(b[i].x); sy.insert(b[i].y);
}
for(auto it : sx) fx[it] = ++nx;
for(auto it : sy) fy[it] = ++ny;
NR = max(nx, ny);
for(int i = 1; i <= n ; ++i) a[i].x = fx[a[i].x], a[i].y = fy[a[i].y];
for(int i = 1; i <= q ; ++i) b[i].x = fx[b[i].x], b[i].y = fy[b[i].y];
sort(a + 1, a + n + 1);
sort(b + 1, b + q + 1);
int j = 1;
arb = new node(1);
for(int i = 1; i <= q ; ++i){
while(j <= n && a[j].z >= b[i].z){
y = a[j].y;
update(a[j].x, arb, 1, y);
++j;
}
yl = b[i].y; yr = ny;
ans[b[i].p] = query(b[i].x, nx, arb, 1, nx);
}
for(int i = 1; i <= q ; ++i) printf("%d\n", ans[i]);
return 0;
}
Compilation message
examination.cpp: In function 'int main()':
examination.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &q);
~~~~~^~~~~~~~~~~~~~~~
examination.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a[i].x, &a[i].y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:111:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &b[i].x, &b[i].y, &b[i].z), b[i].p = i;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2440 ms |
461560 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2440 ms |
461560 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
