Advertisement
a_chn

Untitled

Dec 7th, 2023
890
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.55 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.         pref[i][0] = patches[i][0];
  56.         pref[i][1] = patches[i][1];
  57.         mini = min(mini, pref[i][0]);
  58.         maxi = max(maxi, pref[i][0]);
  59.         pref[i][1]+=pref[i-1][1];
  60.     }
  61.  
  62.     int ii = 1;
  63.     if(mini < r[0].first) {
  64.         int it = 1;
  65.         while(pref[it][0] < r[0].first) {
  66.             it++;
  67.             ii++;
  68.         }
  69.         answers.push_back(make_pair(1, pref[it-1][1]));
  70.         amount.push(pref[it-1][1]);
  71.     }
  72.    
  73.     if(maxi > r[m-2].second) {
  74.         int it = k;
  75.         while(pref[it][0] > r[m-2].second) {
  76.             it--;
  77.         }
  78.         answers.push_back(make_pair(1, pref[k][1]-pref[it][1]));
  79.         amount.push(pref[k][1]-pref[it][1]);
  80.     }
  81.    
  82.     int prev_idx = ii;
  83.  
  84.    
  85.     for(int i = 0; i < m - 1; i++) {
  86.        
  87.         int x = r[i].first, y = r[i].second;
  88.         while(ii <= k && pref[ii][0] <= y) {
  89.             ii++;
  90.         }
  91.         if(prev_idx < ii) {
  92.             r_idx.push_back(make_pair(prev_idx, ii-1));
  93.             sum2[i][1] = pref[ii-1][1]-pref[prev_idx-1][1];
  94.         }
  95.         else {
  96.             r_idx.push_back(make_pair(-1, -1));
  97.         }
  98.         prev_idx = ii;
  99.        
  100.     }
  101.    
  102.     for(int i = 0; i < m - 1; i++) {
  103.         if(r_idx[i].first > 0) {
  104.             int l_bound = r[i].first;
  105.             int r_bound = r[i].second;
  106.             int x = r_idx[i].first, y = r_idx[i].second;
  107.             int it = x;
  108.             int rng = (x+y)/2;
  109.             int sum = 0;
  110.             int diff = y - x;
  111.             while(x < y) {
  112.                 int diff = pref[x][0] - l_bound;
  113.                 int cow = min(pref[y][0], pref[x][0] + diff - 1);
  114.                 while(it <= y && pref[it][0]-cow < r_bound-pref[it][0]) {
  115.                     it++;      
  116.                 }
  117.                 //if(pref[it][0] == r_bound) it--;
  118.                 sum = max(sum, pref[it - 1][1]-pref[x-1][1]);
  119.                 x++;
  120.                
  121.             }
  122.             sum2[i][0] = sum;
  123.         }
  124.     }
  125.    
  126.     for(int i = 0; i < m; i++) {
  127.         amount.push(sum2[i][0]);
  128.         answers.push_back(make_pair(1, sum2[i][0]));
  129.         answers.push_back(make_pair(2, sum2[i][1]-sum2[i][0]));
  130.     }
  131.     sort(answers.begin(), answers.end(), comp);
  132.     int ans = 0;
  133.     for(int i = 0; i < n; i++) {
  134.         ans+=answers[i].second;
  135.     }
  136.     cout << ans << endl;
  137.    
  138. }
  139.  
  140.  
  141.  
  142.  
  143.  
  144.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement