#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
const int MAXQ = 1e5;
const int MAXVAL = 1e9;
int N, Q, ans[MAXQ+10];
pii A[MAXN+10];
struct Data { int x, y, z, num; };
Data B[MAXQ+10];
struct Node1
{
int val; Node1 *lc, *rc;
Node1() : val(0), lc(NULL), rc(NULL) {}
};
struct Node2
{
Node1 *val; Node2 *lc, *rc;
Node2() : val(NULL), lc(NULL), rc(NULL) {}
};
int query1(Node1 *node, int tl, int tr, int xl, int xr)
{
if(xr<tl || tr<xl) return 0;
if(xl<=tl && tr<=xr) return node->val;
int mid=tl+tr>>1;
int ret=0;
if(node->lc!=NULL) ret+=query1(node->lc, tl, mid, xl, xr);
if(node->rc!=NULL) ret+=query1(node->rc, mid+1, tr, xl, xr);
return ret;
}
void update1(Node1 *node, int tl, int tr, int x, int val)
{
if(tl==tr)
{
node->val+=val;
return;
}
int mid=tl+tr>>1;
if(x<=mid)
{
if(node->lc==NULL) node->lc=new Node1();
update1(node->lc, tl, mid, x, val);
}
else
{
if(node->rc==NULL) node->rc=new Node1();
update1(node->rc, mid+1, tr, x, val);
}
int t=0;
if(node->lc!=NULL) t+=node->lc->val;
if(node->rc!=NULL) t+=node->rc->val;
node->val=t;
}
int query2(Node2 *node, int tl, int tr, int yl, int yr, int xl, int xr)
{
if(tr<yl || yr<tl) return 0;
if(yl<=tl && tr<=yr)
{
if(node->val!=NULL) return query1(node->val, 1, MAXVAL, xl, xr);
else return 0;
}
int mid=tl+tr>>1;
int ret=0;
if(node->lc!=NULL) ret+=query2(node->lc, tl, mid, yl, yr, xl, xr);
if(node->rc!=NULL) ret+=query2(node->rc, mid+1, tr, yl, yr, xl, xr);
return ret;
}
void update2(Node2 *node, int tl, int tr, int y, int x, int val)
{
if(node->val==NULL) node->val=new Node1();
if(tl==tr)
{
update1(node->val, 1, MAXVAL, x, val);
return;
}
int mid=tl+tr>>1;
if(y<=mid)
{
if(node->lc==NULL) node->lc=new Node2();
update2(node->lc, tl, mid, y, x, val);
}
else
{
if(node->rc==NULL) node->rc=new Node2();
update2(node->rc, mid+1, tr, y, x, val);
}
int t=0;
if(node->lc!=NULL) t+=query1(node->lc->val, 1, MAXVAL, x, x);
if(node->rc!=NULL) t+=query1(node->rc->val, 1, MAXVAL, x, x);
update1(node->val, 1, MAXVAL, x, t);
}
Node2 *root;
int main()
{
int i, j;
scanf("%d%d", &N, &Q);
for(i=1; i<=N; i++) scanf("%d%d", &A[i].first, &A[i].second);
for(i=1; i<=Q; i++) scanf("%d%d%d", &B[i].x, &B[i].y, &B[i].z), B[i].num=i;
sort(A+1, A+N+1, [&](const pii &p, const pii &q) { return p.first+p.second>q.first+q.second; });
sort(B+1, B+Q+1, [&](const Data &p, const Data &q) { return p.z>q.z; });
root=new Node2();
int it=1;
for(i=1; i<=Q; i++)
{
for(; it<=N && A[it].first+A[it].second>=B[i].z; it++) update2(root, 1, MAXVAL, A[it].second, A[it].first, 1);
ans[B[i].num]=query2(root, 1, MAXVAL, B[i].y, MAXVAL, B[i].x, MAXVAL);
}
for(i=1; i<=Q; i++) printf("%d\n", ans[i]);
}
Compilation message
examination.cpp: In function 'int query1(Node1*, int, int, int, int)':
examination.cpp:34:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
examination.cpp: In function 'void update1(Node1*, int, int, int, int)':
examination.cpp:48:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
examination.cpp: In function 'int query2(Node2*, int, int, int, int, int, int)':
examination.cpp:73:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
examination.cpp: In function 'void update2(Node2*, int, int, int, int, int)':
examination.cpp:88:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
examination.cpp: In function 'int main()':
examination.cpp:109:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
examination.cpp:111: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:112:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(i=1; i<=N; i++) scanf("%d%d", &A[i].first, &A[i].second);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:113:67: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(i=1; i<=Q; i++) scanf("%d%d%d", &B[i].x, &B[i].y, &B[i].z), B[i].num=i;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3120 ms |
442892 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3120 ms |
442892 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
