Description

 

Input

Output

 

Sample Input

32 21 4 23 5 11 4 22 5 13 21 3 12 4 13 5 11 3 22 5 12 21 2 21 2 11 2 11 2 2 

Sample Output

YesNoYes

 

Data Constraint

 

Hint

很明显这是要让我们匹配，很容易想到可以二分图匹配，但是又有数量，于是我们可以网络流，但是n还是巨大，使得我们不得不想想其他办法。

我们的期望搭配就是电阻的允许电压范围跟节点的电压范围接近，于是我们可以贪心。

我们可以用左端点排序，然后对于每个节点找到第一个右端点大于它的，左端点小于等于它的即可。

但是复杂度仍为O(nm),我们可以考虑用map或set维护符合左端点条件的右端点的电阻。复杂度O((n + m) log m + n log n)。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #define N 100005 7 using namespace std; 8 struct data{ 9     int l,r,num,v;10     bool operator < (const data &a) const{11         return (a.r>r);12       }13 }zu[N];14 multiset
            qwq;15 multiset::iterator qaq;16 int n,m,t,ans;17 bool power;18 int read(){19 int x=0,w=1;20 char c=0;21 for (c=getchar();c<'0'||c>'9';c=getchar()) { if (c=='-') w=-1;}22 for (;c>='0'&&c<='9';c=getchar()) x=(x<<3)+(x<<1)+c-'0';23 return x*w;24 }25 bool comp(const struct data a,const struct data b){26 return ((a.l
             
              b.v));27 }28 int main(){29 freopen("machine.in","r",stdin);30 freopen("machine.out","w",stdout);31 for (t=read();t;t--){32 qwq.clear();33 power=true;34 ans=0;35 n=read();36 m=read();37 for(int i=1;i<=n;++i){38 zu[i].l=read();39 zu[i].r=read();40 zu[i].num=read();41 zu[i].v=-1;42 }43 for(int i=n+1;i<=n+m;++i){44 zu[i].l=read();45 zu[i].r=read();46 zu[i].num=read();47 zu[i].v=1;48 }49 sort(zu+1,zu+1+n+m,comp);50 for (int i=1;i<=n+m;i++){51 if (zu[i].v==1) 52 qwq.insert(zu[i]);53 else while (zu[i].num){54 qaq=qwq.lower_bound(zu[i]);55 if (qaq==qwq.end()){56 power=false;57 puts("No");58 break;59 }60 data tmp=*qaq;61 qwq.erase(qaq);62 if (zu[i].num
             
          
         
        
       
      

这种纯考STL的题.......还出了两题

第一次打set，第一次打迭代器，第一次打重载运算符啊啊QAQ