This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<int,int>
#define orta ((bas+son)>>1)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define inf 1000000000
#define N 300005
using namespace std;
#define fpos bos
struct query {
int w,val,id,sg;
};
struct seg {
int s[N<<2];
void up(int node,int bas,int son,int x) {
if(bas==x && son==x) {
s[node]++;
return ;
}
if(orta>=x) up(node<<1,bas,orta,x);
else up(node<<1|1,orta+1,son,x);
s[node]=s[node<<1]+s[node<<1|1];
}
int get(int node,int bas,int son,int x,int y) {
if(bas>y || son<x || x>y) return 0;
if(bas>=x && son<=y) return s[node];
return get(node<<1,bas,orta,x,y)+get(node<<1|1,orta+1,son,x,y);
}
} s[2];
int n,q;
int a2[2][N],cnt[2],ans[N];
vector<query> qu[N];
ii ar[N];
int fpos(int w,int val) {
int bas=1,son=cnt[w];
while(bas<=son) {
if(a2[w][orta]<val) bas=orta+1;
else son=orta-1;
}
return bas;
}
void cmp() {
map<int,int> mp[2];
for(int i=1;i<=n;i++) {
mp[0][ar[i].nd]=1;
mp[1][ar[i].st+ar[i].nd]=1;
}
for(int i=0;i<2;i++) {
for(auto& x:mp[i]) {
a2[i][++cnt[i]]=x.st;
}
}
}
int main() {
scanf("%d %d",&n,&q);
for(int i=1;i<=n;i++) {
int x,y;
scanf("%d %d",&x,&y);
ar[i]={x,y};
}
sort(ar+1,ar+1+n,[](ii a,ii b){return a.st>b.st;});
cmp();
for(int i=1;i<=q;i++) {
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
int bas=1,son=n;
while(bas<=son) {
if(ar[orta].st<=c-b) son=orta-1;
else bas=orta+1;
}
int ul=bas;
bas=1,son=n;
while(bas<=son) {
if(ar[orta].st<a) son=orta-1;
else bas=orta+1;
}
if(ul<=son) {
qu[ul-1].pb({1,c,i,-1});
qu[son].pb({1,c,i,1});
qu[ul-1].pb({0,b,i,1});
}
else {
qu[son].pb({0,b,i,1});
}
}
for(int i=1;i<=n;i++) {
s[0].up(1,1,cnt[0],fpos(0,ar[i].nd));
s[1].up(1,1,cnt[1],fpos(1,ar[i].st+ar[i].nd));
for(auto x:qu[i]) {
ans[x.id]+=x.sg*s[x.w].get(1,1,cnt[x.w],fpos(x.w,x.val),cnt[x.w]);
}
}
for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
}
Compilation message (stderr)
examination.cpp: In function 'int main()':
examination.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&q);
~~~~~^~~~~~~~~~~~~~~
examination.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&x,&y);
~~~~~^~~~~~~~~~~~~~~
examination.cpp:118:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&a,&b,&c);
~~~~~^~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |