Submission #3774215

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define INF 1000000009
typedef pair<int,int>P;
typedef pair<P,P>Q;
vector<Q>vec;
priority_queue<P>pq1;
priority_queue<P>pq2;
priority_queue<P>pq3;
int ans[500009];

int main(){
  int n,m;
  cin>>n>>m;
  for(int i=0;i<m;i++)ans[i]=INF;
  for(int i=0;i<n;i++){
    int a,b,c,w;
    cin>>a>>b>>c>>w;
    vec.push_back(Q(P(w,a),P(b,c)));
  }
  sort(vec.begin(),vec.end());
  reverse(vec.begin(),vec.end());
  for(int i=0;i<m;i++){
    int x,y,z;
    cin>>x>>y>>z;
    pq1.push(P(x,i));
    pq2.push(P(y,i));
    pq3.push(P(z,i));
  }
  for(int i=0;i<vec.size();i++){
    int w=vec[i].fi.fi;
    int a=vec[i].fi.se;
    int b=vec[i].se.fi;
    int c=vec[i].se.se;
    while(!pq1.empty()){
      P now=pq1.top();
      int x=now.fi;
      int idx=now.se;
      if(x<a)break;
      ans[idx]=min(ans[idx],w);
      pq1.pop();
    }
    while(!pq2.empty()){
      P now=pq2.top();
      int y=now.fi;
      int idx=now.se;
      if(y<b)break;
      ans[idx]=min(ans[idx],w);
      pq2.pop();
    }
    while(!pq3.empty()){
      P now=pq3.top();
      int z=now.fi;
      int idx=now.se;
      if(z<c)break;
      ans[idx]=min(ans[idx],w);
      pq3.pop();
    }
  }
  while(!pq1.empty()){
    P now=pq1.top();pq1.pop();
    ans[now.se]=0;
  }
  while(!pq2.empty()){
    P now=pq2.top();pq2.pop();
    ans[now.se]=0;
  }
  while(!pq3.empty()){
    P now=pq3.top();pq3.pop();
    ans[now.se]=0;
  }
  for(int i=0;i<m;i++){
    cout<<ans[i]<<endl;
  }
  return(0);
}

Submission Info

Judge Result