【题解】AcWing 110. 防晒(普及题)

AcWing 110. 防晒

你没有用过的全新OJ

嘿嘿水水题。

题目就是一维坐标轴上给定多个线段，给定多个点，点在线段上造成贡献，点可以重复，问最大贡献

模板题，主要是要注意到给的时候不一定点是互不相同的，所以要记录一下。小心set去重。

//@winlere
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>

using namespace std;  typedef long long ll;
inline int qr(){
      register int ret=0,f=0;
      register char c=getchar();
      while(c<48||c>57)f|=c==45,c=getchar();
      while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar();
      return f?-ret:ret;
}

const int maxn=2505;
struct L{
      int l,r;
      L(){l=r=0;}
      L(const int&a,const int&b){l=a;r=b;}
      inline bool operator <(const L&a)const{return r==a.r?l>a.l:r<a.r;}
}data[maxn];
int cnt[1001],n,m,ans;
set <int> s;

int main(){
      n=qr();m=qr();
      for(register int t=1,t1,t2;t<=n;++t)
        t1=qr(),t2=qr(),data[t]=L(t1,t2);
      for(register int t=1,t1,t2;t<=m;++t){
        t1=qr();t2=qr();
        cnt[t1]+=t2;
        s.insert(t1);
      }
      sort(data+1,data+n+1);
      for(register int t=1;t<=n;++t){
        set<int>::iterator a=s.lower_bound(data[t].l);
        if(a==s.end()||*a>data[t].r) continue;
        if(--cnt[*a]<=0) s.erase(a);
        ++ans;
      }
      printf("%d\n",ans);
      return 0;
}