yicongli

CF854D

Jan 21st, 2021 (edited)
663
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7. #define ll long long
  8.  
  9. template<typename T>
  10. inline void read(T&x){
  11.     x=0;T k=1;char gc;
  12.     while(!isdigit(c)){if(c=='-')k=-1;gc;}
  13.     while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
  14. }
  15.  
  16. const ll INF=5e12;
  17. const int N=1e6+7;
  18.  
  19. struct Airline{
  20.     ll date,city,cost;
  21. };
  22.  
  23. inline bool cmp(const Airline &a,const Airline &b){
  24.     return a.date<b.date;
  25. }
  26.  
  27. ll CostA[N];
  28. ll CostB[N];
  29. ll MinCost[N];
  30. vector<Airline>A,B;
  31.  
  32. int main(){
  33.     // freopen(".in","r",stdin);
  34.     // freopen(".out","w",stdout);
  35.     int n,m,k;r(n),r(m),r(k);
  36.     int MaxA=0;
  37.     int MaxB=0;
  38.     int MinA=1e6;
  39.     int MinB=1e6;
  40.     for(int i=1;i<=m;++i){
  41.         int d,f,t,c;r(d),r(f),r(t),r(c);
  42.         if(f)A.push_back(Airline{d,f,c}),MaxA=max(MaxA,d),MinA=min(MinA,d);
  43.         else B.push_back(Airline{d,t,c}),MaxB=max(MaxB,d),MinB=min(MinB,d);
  44.     }
  45.     sort(A.begin(),A.end(),cmp);
  46.     sort(B.begin(),B.end(),cmp);
  47.     ll sum=n*INF;
  48.     for(int i=1;i<=n;++i)MinCost[i]=INF;
  49.     for(int i=0;i<MinA;++i)CostA[i]=sum;
  50.     for(int i=MinA,j=0;i<=MaxA;++i){
  51.         while(j<A.size()&&i>=A[j].date){
  52.             sum-=MinCost[A[j].city];
  53.             MinCost[A[j].city]=min(MinCost[A[j].city],A[j].cost);
  54.             sum+=MinCost[A[j].city];
  55.             j++;
  56.         }
  57.         CostA[i]=min(CostA[i-1],sum);
  58.     }
  59.     for(int i=MaxA+1;i<=MaxB;++i)CostA[i]=CostA[i-1];
  60.     sum=n*INF;
  61.     ll ans=2*n*INF;
  62.     for(int i=1;i<=n;++i)MinCost[i]=INF;
  63.     for(int i=MaxB,j=B.size()-1;i>=MinB;--i){
  64.         while(j>=0&&i<=B[j].date){
  65.             sum-=MinCost[B[j].city];
  66.             MinCost[B[j].city]=min(MinCost[B[j].city],B[j].cost);
  67.             sum+=MinCost[B[j].city];
  68.             j--;
  69.         }
  70.         CostB[i]=sum;
  71.         if(i-k-1>0){
  72.             ans=min(ans,CostB[i]+CostA[i-k-1]);
  73.         }
  74.     }
  75.     if(ans>INF)ans=-1;
  76.     printf("%lld\n",ans);
  77.     return 0;
  78. }
RAW Paste Data