Submission #1223860

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define ff first
#define ss second
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
typedef pair<in,in> PII;
vector<pair<PII,in> > evt;
vector<PII> rvt;
set<PII> cnu;
VI obv;
multiset<in> bd;
in bssc=0;
VI rbd;
VI bnus;
VI prtof;
VI typof;
VI usd;
void imp(){
  in q;
  cin>>q;
  forn(z,q)
    cout<<"-1\n";
  exit(0);
}
in vlof(in cc){
  cc=lower_bound(all(rbd),cc)-rbd.begin();
  if(cc==sz(bnus))
    return -1;
  in cv=bnus[cc];
  if(cv<0)
    return -1;
  return cv+bssc;
}
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  in n;
  cin>>n;
  in a,b;
  rvt.resize(n);
  usd.resize(n);
  forn(z,n){
    cin>>a>>b;
    rvt[z]=MP(b,a);
    if(a<=b){
      obv.PB(a);
      continue;
    }
    evt.PB(MP(MP(a,z),1));
    evt.PB(MP(MP(b,z),0));
  }
  forn(z,n+1){
    cin>>a;
    bd.insert(a);
  }
  bssc=sz(obv);
  forv(i,obv){
    auto it=bd.lower_bound(obv[i]);
    if(it==bd.end()){
      imp();
    }
    bd.erase(it);
  }
  fors(i,bd)
    rbd.PB(*i);
  n=sz(rbd);
  prtof.resize(n,-1);
  typof.resize(n,-1);
  bnus.resize(n);
  const in inf=1e7;
  sort(all(evt));
  in nxev=0;
  in nd;
  obv.clear();
  in bdbl=-1;
  forv(z,rbd){
    nd=rbd[z];
    while(nxev<sz(evt) && evt[nxev].ff.ff<=nd){
      if(evt[nxev].ss==0){
	cnu.insert(MP(rvt[evt[nxev].ff.ss].ss,evt[nxev].ff.ss));
      }
      else{
	if(!usd[evt[nxev].ff.ss]){
	  cnu.erase(evt[nxev].ff);
	  ++bssc;
	  obv.PB(evt[nxev].ff.ss);
	}
      }
      ++nxev;
    }
    if(sz(obv)>0){
      prtof[z]=obv.back();
      typof[z]=1;
      obv.pop_back();
      continue;
    }
    if(sz(cnu)==0){
      if(bdbl!=-1)
	imp();
      bdbl=z;
      continue;
    }
    auto it=cnu.end();
    --it;
    prtof[z]=it->second;
    typof[z]=0;
    usd[it->second]=1;
    cnu.erase(it);
  }
  assert(bdbl!=-1);
  bnus[bdbl]=0;
  for(in i=bdbl+1;i<sz(bnus);++i)
    bnus[i]=-inf;
  in cc;
  for(in i=bdbl-1;i>=0;--i){
    bnus[i]=bnus[i+1];
    if(typof[i]==0){
      cc=rvt[prtof[i]].ss;
      cc=lower_bound(all(rbd),cc)-rbd.begin();
      if(cc<sz(bnus))
	bnus[i]=max(bnus[i],bnus[cc]+1);
    }
  }
  in q;
  cin>>q;
  in ca,cb;
  forn(z,q){
    cin>>ca>>cb;
    in c1=vlof(ca);
    if(c1!=-1)
      ++c1;
    cout<<max(c1,vlof(cb))<<"\n";
  }
  return 0;
}

Submission Info

Judge Result