AOJ 2426 Treasure Hunt

#include<bits/stdc++.h>
#define fi first
#define se second
#define show(x) cerr<<#x<<"="<<x<<"\n"
typedef long long ll;
using namespace std;
//const ll MOD=(ll)1e9+7;
//const ll inf=(ll)1e14;
const int dy[]={1,0,-1};
const int dx[]={1,0,-1};
int n,m,h,w;
vector<int> x,y,xx,yy;
int imos[5011][5011];

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout<<fixed;
#ifdef LOCAL_DEFINE
  FILE *stream1;
  //FILE *stream2;
  stream1=freopen("in","r",stdin);
  //stream2=freopen("out","w",stdout);
  if(stream1==NULL)return 0;
  //if(stream2==NULL)return 0;
#endif
  cin>>n>>m;
  for(int i=0;i<n;i++){
    int a,b;cin>>a>>b;
    xx.push_back(a);
    x.push_back(a);
    yy.push_back(b);
    y.push_back(b);
  }
  x.push_back(-1000000001);
  y.push_back(-1000000001);
  x.push_back(1000000001);
  y.push_back(1000000001);
  sort(x.begin(),x.end());
  sort(y.begin(),y.end());
  x.erase(unique(x.begin(),x.end()),x.end());
  y.erase(unique(y.begin(),y.end()),y.end());
  for(int i=0;i<n;i++){
    xx[i]=lower_bound(x.begin(),x.end(),xx[i])-x.begin();
    yy[i]=lower_bound(y.begin(),y.end(),yy[i])-y.begin();
  }
  h=(int)y.size();
  w=(int)x.size();
  for(int i=0;i<n;i++){
    imos[yy[i]][xx[i]]++;
  }
  for(int i=0;i<h;i++)for(int j=1;j<w;j++)imos[i][j]+=imos[i][j-1];
  for(int i=1;i<h;i++)for(int j=0;j<w;j++)imos[i][j]+=imos[i-1][j];
  for(int i=0;i<m;i++){
    int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;
    auto xa=lower_bound(x.begin(),x.end(),x1);
    if(*xa>=x1)xa--;
    auto xb=lower_bound(x.begin(),x.end(),x2);
    if(*xb>x2)xb--;
    auto ya=lower_bound(y.begin(),y.end(),y1);
    if(*ya>=y1)ya--;
    auto yb=lower_bound(y.begin(),y.end(),y2);
    if(*yb>y2)yb--;
    x1=xa-x.begin();x2=xb-x.begin();y1=ya-y.begin();y2=yb-y.begin();
    cout<<imos[y2][x2]-imos[y2][x1]-imos[y1][x2]+imos[y1][x1]<<endl;
  }
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}

• 座標圧縮を初めてやった気がしたぉ。
• 面白いなこれ。