Submission #119243

#	Time	Username	Problem	Language	Result	Execution time	Memory
119243		KLPP	Examination (JOI19_examination)	C++14	100 / 100	1647 ms	42500 KiB

examination

#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;
}

Compilation message (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);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57