이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
typedef long long int lld;
typedef pair<lld,lld> pii;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
#define MAX 1000000000
struct query{
lld A,B,C;
int index;
};
bool operator<(query a, query b){
if(a.C<b.C)return true;
return false;
}
class FT{
int arr[300000];
int n;
public:
void init(int N){
n=N;
rep(i,0,n+1)arr[i]=0;
}
void update(int pos, int val){
for(int i=pos;i<=n;i+=(i&(-i))){
arr[i]+=val;
}
}
int query(int pos){
int ans=0;
for(int i=pos;i>0;i-=(i&(-i))){
ans+=arr[i];
}
return ans;
}
};
class ANS{
pii points[100000];
pair<pii,int> queries[100000];
int n,q;
vector<int> A,B;
int respostas[100000];
public:
void init(int N,int Q,pii A[], pii B[]){
n=N;
rep(i,0,n){
points[i]=A[i];
}
q=Q;
rep(i,0,q){
queries[i]=pair<pii,int>(B[i],i);
}
}
int BSA(lld x){
int lo,hi;
lo=0;
hi=A.size()-1;
while(hi-lo>0){
//cout<<lo<<" "<<hi<<endl;
int mid=(hi+lo)/2;
if(A[mid]==x)return mid;
if(A[mid]<x)lo=mid+1;
else hi=mid-1;
}
return lo;
}
int BSB(lld x){
int lo,hi;
lo=0;
hi=B.size()-1;
while(hi-lo>0){
//cout<<lo<<" "<<hi<<endl;
int mid=(hi+lo)/2;
if(B[mid]==x)return mid;
if(B[mid]<x)lo=mid+1;
else hi=mid-1;
}
return lo;
}
void compress(){
set<int> a,b;
rep(i,0,n){
a.insert(points[i].first);
b.insert(points[i].second);
}
rep(i,0,q){
a.insert(queries[i].first.first);
b.insert(queries[i].first.second);
}
trav(x,a){
A.push_back(x);
}
trav(y,b){
B.push_back(y);
}
//cout<<"A"<<endl;
rep(i,0,n){
//cout<<points[i].first<<" "<<points[i].second<<endl;
points[i].first=BSA(points[i].first)+1;
points[i].second=BSB(points[i].second)+1;
//cout<<points[i].first<<" "<<points[i].second<<endl;
}
rep(i,0,q){
queries[i].first.first=BSA(queries[i].first.first)+1;
queries[i].first.second=BSB(queries[i].first.second)+1;
}
sort(points,points+n);
sort(queries,queries+q);
FT *F=new FT();
F->init(B.size());
int pnt=n-1;
for(int i=q-1;i>-1;i--){
while(pnt>=0 && points[pnt].first>=queries[i].first.first){
F->update(points[pnt].second,+1);
pnt--;
}
respostas[queries[i].second]=n-pnt-1-F->query(queries[i].first.second-1);
}
}
int responder(int q){
return respostas[q];
}
void clear(){
A.clear();
B.clear();
}
};
int main(){
int n,q;
scanf("%d %d",&n,&q);
pii arr[n];
rep(i,0,n){
scanf("%lld %lld",&arr[i].first,&arr[i].second);
}
sort(arr,arr+n);
query Q[q];
rep(i,0,q){
scanf("%lld %lld %lld",&Q[i].A,&Q[i].B,&Q[i].C);
Q[i].C=max(Q[i].C,Q[i].A+Q[i].B);
Q[i].index=i;
}
ANS *X=new ANS();
int answer[q];
rep(i,0,q)answer[i]=0;
//cout<<"A"<<endl;
pii A[n];
pii B[q];
rep(i,0,n){
A[i].first=arr[i].first;
A[i].second=arr[i].first+arr[i].second;
}
rep(i,0,q){
B[i].first=Q[i].A;
B[i].second=Q[i].C;
}
//cout<<"A"<<endl;
X->init(n,q,A,B);
//cout<<"A"<<endl;
X->compress();
X->clear();
//cout<<"A"<<endl;
rep(i,0,q){
answer[i]+=X->responder(i);
//cout<<answer[i]<<endl;
}
rep(i,0,n){
A[i].first=arr[i].first;
A[i].second=arr[i].first+arr[i].second;
}
rep(i,0,q){
B[i].first=Q[i].C-Q[i].B;
B[i].second=Q[i].C;
}
//cout<<"A"<<endl;
X->init(n,q,A,B);
//cout<<"A"<<endl;
X->compress();
X->clear();
//cout<<"A"<<endl;
rep(i,0,q){
answer[i]-=X->responder(i);
//cout<<answer[i]<<endl;
}
rep(i,0,n){
A[i].first=arr[i].first;
A[i].second=arr[i].second;
}
rep(i,0,q){
B[i].first=Q[i].C-Q[i].B;
B[i].second=Q[i].B;
}
//cout<<"A"<<endl;
X->init(n,q,A,B);
//cout<<"A"<<endl;
X->compress();
X->clear();
//cout<<"A"<<endl;
rep(i,0,q){
answer[i]+=X->responder(i);
//cout<<answer[i]<<endl;
}
rep(i,0,q)printf("%d\n",answer[i]);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
examination.cpp: In function 'int main()':
examination.cpp:132:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&q);
~~~~~^~~~~~~~~~~~~~~
examination.cpp:135:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld",&arr[i].first,&arr[i].second);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:140:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld %lld",&Q[i].A,&Q[i].B,&Q[i].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... |