#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sortvec(x) sort(all(x))
#define compress(x) x.erase(unique(all(x)), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
const LL llinf=1987654321987654321;
const int inf=2000000000;
struct FENWICK{
int tree[200010];
int sum(int i){
LL ans=0;
while(i){
ans+=tree[i];
i-=(i&-i);
}
return ans;
}
void update(int i, int num){
while(i<=200000){
tree[i]+=num;
i+=(i&-i);
}
}
void cl(){memset(tree, 0, sizeof tree);}
}fen;
pair<pli, pll> query[200010];
vector<LL> idx, idy;
int ans[200010], n, q;
bool comp(pair<pli, pll> a, pair<pli, pll> b){
if(a.F.F!=b.F.F)return a.F.F>b.F.F;
return a.F.S<b.F.S;
}
vector<pll> upd;
vector<pair<pll, int> > que;
void DNC(int l, int r){
if(l==r)return;
int mid=(l+r)/2;
DNC(l, mid); DNC(mid+1, r);
upd.clear(); que.clear();
for(int i=l; i<=mid; i++){
if(!query[i].F.S)upd.pb(query[i].S);
}
for(int i=mid+1; i<=r; i++){
if(query[i].F.S)que.pb(mp(query[i].S, query[i].F.S));
}
sort(all(upd), greater<pll>());
sort(all(que), greater<pair<pll, int> >());
int pv=0;
for(auto i:que){
for(; pv<upd.size(); pv++){
if(upd[pv].F<i.F.F)break;
fen.update((int)upd[pv].S, 1);
}
ans[i.S]+=fen.sum(200000)-fen.sum(i.F.S-1);
}
for(auto i:upd)fen.update(i.S, -1);
}
int main(){
scanf("%d %d", &n, &q);
for(int i=1; i<=n; i++){
scanf("%lld %lld", &query[i].F.F, &query[i].S.F);
query[i].S.S=query[i].F.F+query[i].S.F;
idx.pb(query[i].S.F);
idy.pb(query[i].S.S);
}
for(int i=n+1; i<=n+q; i++){
scanf("%lld %lld %lld", &query[i].F.F, &query[i].S.F, &query[i].S.S);
query[i].F.S=i-n;
idx.pb(query[i].S.F);
idy.pb(query[i].S.S);
}
sort(query+1, query+n+q+1, comp);
sortvec(idx); sortvec(idy);
compress(idx); compress(idy);
for(int i=1; i<=n+q; i++){
query[i].S.F=lower_bound(all(idx), query[i].S.F)-idx.begin()+1;
query[i].S.S=lower_bound(all(idy), query[i].S.S)-idy.begin()+1;
}
DNC(1, n+q);
for(int i=1; i<=q; i++)printf("%d\n", ans[i]);
}
Compilation message
examination.cpp: In function 'void DNC(int, int)':
examination.cpp:59:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; pv<upd.size(); pv++){
~~^~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:68: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:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld", &query[i].F.F, &query[i].S.F);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld %lld", &query[i].F.F, &query[i].S.F, &query[i].S.S);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
359 ms |
16596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
359 ms |
16596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
