Advertisement
a_chn

Untitled

Dec 7th, 2023
795
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.46 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. int k, m, n;
  5. int nohj[200005];
  6. array<int, 2> patches[200005];
  7. int pref[200005][2];
  8. int sum2[200005][2];
  9. bool visited[200005];
  10. set<int> exists;
  11. priority_queue<int> amount;
  12.  
  13. vector<pair<int, int> > answers;
  14.  
  15. vector<pair<int, int> > r;
  16. vector<pair<int, int> > r_idx;
  17.  
  18. bool comp(const pair<int, int>& a, const pair<int, int>& b) {
  19.     if (a.second == b.second) {
  20.         return a.first < b.first;
  21.     }
  22.     return a.second > b.second;
  23. }
  24.  
  25. void setIO(string s) {
  26.     ios_base::sync_with_stdio(0);
  27.     cin.tie(0);
  28.     freopen((s + ".in").c_str(), "r", stdin);
  29.     freopen((s + ".out").c_str(), "w", stdout);
  30. }
  31.  
  32. signed main() {
  33.     // setIO("test");
  34.     int mini = LLONG_MAX, maxi = LLONG_MIN;
  35.     cin >> k >> m >> n;
  36.     for(int i = 1; i <= k; i++) {
  37.         cin >> patches[i][0] >> patches[i][1];
  38.     }
  39.    
  40.     sort(patches + 1, patches + 1 + k);
  41.    
  42.     int prev = 0;
  43.     for(int i = 1; i <= m; i++) {
  44.         cin >> nohj[i];
  45.         exists.insert(nohj[i]);
  46.     }
  47.  
  48.     sort(nohj + 1, nohj + m + 1);
  49.  
  50.     for(int i = 2; i <= m; ++i) {
  51.         r.push_back(make_pair(nohj[i - 1], nohj[i]));
  52.     }
  53.    
  54.     for(int i = 1; i <= k; i++) {
  55.         if(exists.find(patches[i][0]) != exists.end()) patches[i][1] = 0;
  56.         pref[i][0] = patches[i][0];
  57.         pref[i][1] = patches[i][1];
  58.         mini = min(mini, pref[i][0]);
  59.         maxi = max(maxi, pref[i][0]);
  60.         pref[i][1]+=pref[i-1][1];
  61.     }
  62.  
  63.     int ii = 1;
  64.     if(mini < r[0].first) {
  65.         int it = 1;
  66.         while(pref[it][0] < r[0].first) {
  67.             it++;
  68.             ii++;
  69.         }
  70.         answers.push_back(make_pair(1, pref[it-1][1]));
  71.         amount.push(pref[it-1][1]);
  72.     }
  73.    
  74.     if(maxi > r[m-2].second) {
  75.         int it = k;
  76.         while(pref[it][0] > r[m-2].second) {
  77.             it--;
  78.         }
  79.         answers.push_back(make_pair(1, pref[k][1]-pref[it][1]));
  80.         amount.push(pref[k][1]-pref[it][1]);
  81.     }
  82.    
  83.     int prev_idx = ii;
  84.  
  85.    
  86.     for(int i = 0; i < m - 1; i++) {
  87.        
  88.         int x = r[i].first, y = r[i].second;
  89.         while(ii <= k && pref[ii][0] > x && pref[ii][0] < y) {
  90.             ii++;
  91.         }
  92.         if(prev_idx < ii) {
  93.             r_idx.push_back(make_pair(prev_idx, ii-1));
  94.             sum2[i][1] = pref[ii-1][1]-pref[prev_idx-1][1];
  95.         }
  96.         else {
  97.             r_idx.push_back(make_pair(-1, -1));
  98.         }
  99.         prev_idx = ii;
  100.        
  101.     }
  102.    
  103.     for(int i = 0; i < m - 1; i++) if(r_idx[i].first > 0) {
  104.         int r_bound = r[i].second;
  105.         int x = r_idx[i].first, y = r_idx[i].second;
  106.         int it = x;
  107.         int rng = (x+y)/2;
  108.         int sum = 0;
  109.         for(int j = 0; j <= y-x; j++) {
  110.             while(it <= k && pref[it][0]-pref[x][0] < r_bound-pref[it][0] && pref[it][0] < r_bound) {
  111.                 it++;      
  112.             }
  113.             //if(pref[it][0] == r_bound) it--;
  114.             it--;
  115.             sum = max(sum, pref[it][1]-pref[x-1][1]);
  116.             x++;
  117.            
  118.         }
  119.         sum2[i][0] = sum;
  120.  
  121.        
  122.     }
  123.    
  124.     for(int i = 0; i < m; i++) {
  125.         amount.push(sum2[i][0]);
  126.         answers.push_back(make_pair(1, sum2[i][0]));
  127.         answers.push_back(make_pair(2, sum2[i][1]-sum2[i][0]));
  128.     }
  129.     sort(answers.begin(), answers.end(), comp);
  130.     int ans = 0;
  131.     for(int i = 0; i < n; i++) {
  132.         ans+=answers[i].second;
  133.     }
  134.     cout << ans << endl;
  135.    
  136. }
  137.  
  138.  
  139.  
  140.  
  141.  
  142.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement