Codeforces Round #523 (Div. 2)D（二分，多重集）

#include<bits/stdc++.h>
using namespace std;
const long long N=1e5+5;
const long long MOD=1e9+7;
long long n,x,y,ans=0;
long long cost[N];
pair<long long,long long>a[N];
multiset<pair<pair<long long,long long>,long long> >s;
int main(){
cin>>n>>x>>y;
for(long long i=1;i<=n;i++){
  cin>>a[i].first>>a[i].second;
  s.insert({{a[i].second,a[i].first},i});
}
sort(a+1,a+n+1);
for(long long i=1;i<=n;i++){
  cost[i]=(x+y*(a[i].second-a[i].first));
  if(!s.size()||s.begin()->first.first>=a[i].first)
   continue;
  auto it=s.lower_bound({{a[i].first,0},0});//自动二分查找到大于等于a[i].first的a[j].second
  long long pre=(--it)->first.first;//最有可能可以不用开一台新电视的节目
  if(y*(a[i].second-pre)>=cost[i])
   continue;
  cost[i]=y*(a[i].second-pre);
  s.erase(it);
}
for(long long i=1;i<=n;i++){
  ans+=cost[i];
  ans%=MOD;
}
ans%=MOD;
cout<<ans;
}
//轻微思维加上二分，多重集的便利可见一斑，手写二分中遭遇不测~

巴特西

Codeforces Round #523 (Div. 2)D（二分，多重集）

最新文章

热门文章