이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int M=4e6;
int b[N],sum[N],cnt=0,froot[N],sroot[N];
pair<int,int> arr[N];
struct{
int l,r;
long long val;
}s[M];
int clone(int x){s[++cnt]=s[x]; return cnt;}
struct persist{
int build(int l,int r,int idx){
if(l==r){
s[idx]={0,0,0};
return idx;
}
int m=(l+r)/2;
s[idx].l=build(l,m,++cnt);
s[idx].r=build(m+1,r,++cnt);
s[idx].val=s[s[idx].l].val+s[s[idx].r].val;
return idx;
}
int update(int l,int r,int idx,int a,int b){
int now=clone(idx);
if(l==r){
s[now].val+=b;
return now;
}
int m=(l+r)/2;
if(a<=m) s[now].l=update(l,m,s[idx].l,a,b);
else s[now].r=update(m+1,r,s[idx].r,a,b);
s[now].val=s[s[now].l].val+s[s[now].r].val;
return now;
}
int query(int l,int r,int idx,int a,int b){
if(a>r || b<l) return 0;
if(a<=l && b>=r) return s[idx].val;
int m=(l+r)/2;
return query(l,m,s[idx].l,a,b)+query(m+1,r,s[idx].r,a,b);
}
}ftree,stree;
int main(){
int n,q;
cin>>n >>q;
for(int i=1;i<=n;i++){
cin>>arr[i].first >>arr[i].second;
b[i]=arr[i].second;
sum[i]=arr[i].first+arr[i].second;
}
sort(arr+1,arr+n+1);
sort(b+1,b+n+1);
sort(sum+1,sum+n+1);
froot[0]=ftree.build(1,n,++cnt);
sroot[0]=stree.build(1,n,++cnt);
for(int i=1;i<=n;i++){
int tb=lower_bound(b+1,b+n+1,arr[i].second)-b;
int ts=lower_bound(sum+1,sum+n+1,arr[i].first+arr[i].second)-sum;
cout<<tb <<" " <<ts <<"\n";
froot[i]=ftree.update(1,n,froot[i-1],tb,1);
sroot[i]=stree.update(1,n,sroot[i-1],ts,1);
}
while(q--){
int x,y,z,ans=0;
cin>>x >>y >>z;
int ta=lower_bound(arr+1,arr+n+1,make_pair(x,0))-arr;
int md=lower_bound(arr+ta,arr+n+1,make_pair(z-y,0))-arr;
int fb=lower_bound(b+1,b+n+1,y)-b;
int fs=lower_bound(sum+1,sum+n+1,z)-sum;
ans+=ftree.query(1,n,froot[n],fb,n)-ftree.query(1,n,froot[md-1],fb,n);
ans+=stree.query(1,n,sroot[md-1],fs,n)-stree.query(1,n,sroot[ta-1],fs,n);
cout<<ans <<"\n";
}
}
# | 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... |