제출 #119243

#제출 시각아이디문제언어결과실행 시간메모리
119243KLPPExamination (JOI19_examination)C++14
100 / 100
1647 ms42500 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...