제출 #1299960

#제출 시각아이디문제언어결과실행 시간메모리
1299960qs1Examination (JOI19_examination)C++20
2 / 100
3091 ms24608 KiB
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define tp tuple<lli,lli,lli,lli,lli>


int main(){
  lli x,y,n,an,bn,cn;
  cin>>x>>y;
  set<pair<lli,lli>>la,lb,lc;
  vector<lli>vn(x,0),vr(y);
  vector<tp>vt(y);
  la.insert({-1,-1});
  lb.insert({-1,-1});
  lc.insert({-1,-1});
  for(lli i=0;i<x;i++){
    cin>>an>>bn;
    la.insert({an,i});
    lb.insert({bn,i});
    lc.insert({an+bn,i});
  }
  for(lli i=0;i<y;i++){
    cin>>an>>bn>>cn;
    vt[i]={an/sqrt(x),bn,an,cn,i};
  }
  sort(vt.begin(),vt.end());
  auto a=la.begin(),b=lb.begin(),c=lc.begin();
  auto af=la.end(),bf=lb.end(),cf=lc.end();
  af--;
  bf--;
  cf--;
  
  n=x;
  for(tp t:vt){
    an=get<2>(t);
    bn=get<1>(t);
    cn=get<3>(t);
    while(a!=af&&(*a).first<an){
      a++;
      vn[(*a).second]++;
      if(vn[(*a).second]==1)n--;
    }
    while((*a).first>=an){
      vn[(*a).second]--;
      if(vn[(*a).second]==0)n++;
      a--;
    }
    while(b!=bf&&(*b).first<bn){
      b++;
      vn[(*b).second]++;
      if(vn[(*b).second]==1)n--;
    }
    while((*b).first>=bn){
      vn[(*b).second]--;
      if(vn[(*b).second]==0)n++;
      b--;
    }
    while(c!=cf&&(*c).first<cn){
      c++;
      vn[(*c).second]++;
      if(vn[(*c).second]==1)n--;
    }
    while((*c).first>=cn){
      vn[(*c).second]--;
      if(vn[(*c).second]==0)n++;
      c--;
    }
    vr[get<4>(t)]=n;
  }
  for(auto i:vr)cout<<i<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...