Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define int long long
- int k, m, n;
- int nohj[200005];
- array<int, 2> patches[200005];
- int pref[200005][2];
- int sum2[200005][2];
- bool visited[200005];
- set<int> exists;
- priority_queue<int> amount;
- vector<pair<int, int> > answers;
- vector<pair<int, int> > r;
- vector<pair<int, int> > r_idx;
- bool comp(const pair<int, int>& a, const pair<int, int>& b) {
- if (a.second == b.second) {
- return a.first < b.first;
- }
- return a.second > b.second;
- }
- void setIO(string s) {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- freopen((s + ".in").c_str(), "r", stdin);
- freopen((s + ".out").c_str(), "w", stdout);
- }
- signed main() {
- // setIO("test");
- int mini = LLONG_MAX, maxi = LLONG_MIN;
- cin >> k >> m >> n;
- for(int i = 1; i <= k; i++) {
- cin >> patches[i][0] >> patches[i][1];
- }
- sort(patches + 1, patches + 1 + k);
- int prev = 0;
- for(int i = 1; i <= m; i++) {
- cin >> nohj[i];
- exists.insert(nohj[i]);
- }
- sort(nohj + 1, nohj + m + 1);
- for(int i = 2; i <= m; ++i) {
- r.push_back(make_pair(nohj[i - 1], nohj[i]));
- }
- for(int i = 1; i <= k; i++) {
- if(exists.find(patches[i][0]) != exists.end()) patches[i][1] = 0;
- pref[i][0] = patches[i][0];
- pref[i][1] = patches[i][1];
- mini = min(mini, pref[i][0]);
- maxi = max(maxi, pref[i][0]);
- pref[i][1]+=pref[i-1][1];
- }
- int ii = 1;
- if(mini < r[0].first) {
- int it = 1;
- while(pref[it][0] < r[0].first) {
- it++;
- ii++;
- }
- answers.push_back(make_pair(1, pref[it-1][1]));
- amount.push(pref[it-1][1]);
- }
- if(maxi > r[m-2].second) {
- int it = k;
- while(pref[it][0] > r[m-2].second) {
- it--;
- }
- answers.push_back(make_pair(1, pref[k][1]-pref[it][1]));
- amount.push(pref[k][1]-pref[it][1]);
- }
- int prev_idx = ii;
- for(int i = 0; i < m - 1; i++) {
- int x = r[i].first, y = r[i].second;
- while(ii <= k && pref[ii][0] > x && pref[ii][0] < y) {
- ii++;
- }
- if(prev_idx < ii) {
- r_idx.push_back(make_pair(prev_idx, ii-1));
- sum2[i][1] = pref[ii-1][1]-pref[prev_idx-1][1];
- }
- else {
- r_idx.push_back(make_pair(-1, -1));
- }
- prev_idx = ii;
- }
- for(int i = 0; i < m - 1; i++) if(r_idx[i].first > 0) {
- int r_bound = r[i].second;
- int x = r_idx[i].first, y = r_idx[i].second;
- int it = x;
- int rng = (x+y)/2;
- int sum = 0;
- for(int j = 0; j <= y-x; j++) {
- while(it <= k && pref[it][0]-pref[x][0] < r_bound-pref[it][0] && pref[it][0] < r_bound) {
- it++;
- }
- //if(pref[it][0] == r_bound) it--;
- it--;
- sum = max(sum, pref[it][1]-pref[x-1][1]);
- x++;
- }
- sum2[i][0] = sum;
- }
- for(int i = 0; i < m; i++) {
- amount.push(sum2[i][0]);
- answers.push_back(make_pair(1, sum2[i][0]));
- answers.push_back(make_pair(2, sum2[i][1]-sum2[i][0]));
- }
- sort(answers.begin(), answers.end(), comp);
- int ans = 0;
- for(int i = 0; i < n; i++) {
- ans+=answers[i].second;
- }
- cout << ans << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement