Advertisement
OIQ

I

OIQ
Dec 2nd, 2019
212
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <utility>
  4. #include <set>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8. typedef long long ll;
  9.  
  10. bool comp(pair <ll, pair<ll, ll> > a, pair <int, pair<ll, ll> > b) {
  11.     if (a.second.second > b.second.second)
  12.         return true;
  13.     else if (a.second.second < b.second.second)
  14.         return  false;
  15.     else {
  16.         if (a.second.first < b.second.first)
  17.             return true;
  18.         return false;
  19.     }
  20. }
  21.  
  22. signed int main() {
  23.  
  24.     ll n;
  25.  
  26.     cin >> n;
  27.  
  28.     vector <pair < ll, pair<ll, ll> > > v(n);
  29.  
  30.     for (int i = 0; i < n; i++) {
  31.         int a, b;
  32.         cin >> a >> b;
  33.  
  34.         v[i] = { i, {a, b} };
  35.     }
  36.  
  37.     sort(v.begin(), v.end(), comp);
  38.  
  39.  
  40.     set <ll> s;
  41.  
  42.     for (int i = 1; i < n + 1; i++)
  43.         s.insert(i);
  44.  
  45.     vector <ll> curr(n + 1, -1);
  46.  
  47.  
  48.     vector <ll> st;
  49.     long long ans = 0;
  50.  
  51.     for (int i = 0; i < n; i++) {
  52.         set<ll>::iterator t = s.lower_bound(v[i].second.first);
  53.         if (*t == v[i].second.first) {
  54.             //c++;
  55.             s.erase(*t);
  56.             curr[v[i].first] = *t;
  57.             v[i].first = -1;
  58.             continue;
  59.         }
  60.         else if (t == s.begin()) {
  61.             if (*t == v[i].second.first) {
  62.                 //c++;
  63.                 s.erase(*t);
  64.                 curr[v[i].first] = *t;
  65.                 v[i].first = -1;
  66.             }
  67.             else {
  68.                 ans += v[i].second.second;
  69.             }
  70.         }
  71.         else {
  72.             //c++;
  73.             t--;
  74.             s.erase(*t);
  75.             curr[v[i].first] = *t;
  76.             v[i].first = -1;
  77.         }
  78.     }
  79.  
  80.     cout << ans << endl;
  81.  
  82.  
  83.     for (int i = 0; i < n; i++) {
  84.         if (v[i].first != -1) {
  85.             auto t = s.begin();
  86.             curr[v[i].first] = *t;
  87.             s.erase(*t);
  88.         }
  89.     }
  90.  
  91.     for (int i = 0; i < n; i++)
  92.         cout << curr[i] << " ";
  93.  
  94.  
  95.     return 0;
  96. }
Advertisement
RAW Paste Data Copied
Advertisement