Advertisement
OIQ

xd

OIQ
Nov 30th, 2019
194
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.  
  9. bool comp(pair <int, pair<int, int>> a, pair <int, pair<int, int>> b) {
  10.     if (a.second.second > b.second.second)
  11.         return true;
  12.     else if (a.second.second < b.second.second)
  13.         return  false;
  14.     else {
  15.         if (a.second.first < b.second.first)
  16.             return true;
  17.         return false;
  18.     }
  19. }
  20.  
  21. int main() {
  22.  
  23.     int n;
  24.  
  25.     cin >> n;
  26.  
  27.     vector <pair < int, pair<int, int>>> v(n);
  28.  
  29.     for (int i = 0; i < n; i++) {
  30.         int a, b;
  31.         cin >> a >> b;
  32.  
  33.         v[i] = { i, {a, b} };
  34.     }
  35.  
  36.     sort(v.begin(), v.end(), comp);
  37.  
  38.  
  39.     set <int> s;
  40.  
  41.     for (int i = 1; i < 200001; i++)
  42.         s.insert(i);
  43.  
  44.     vector <int> curr(n, -1);
  45.  
  46.  
  47.     vector <int> st;
  48.     long long ans = 0;
  49.     //int c = 0;
  50.  
  51.     for (int i = 0; i < n; i++) {
  52.         auto t = s.lower_bound(v[i].second.first);
  53.         if (*t == v[i].second.first) {
  54.             //c++;
  55.             s.erase(v[i].second.first);
  56.             curr[v[i].first] = t&;
  57.             //st.push_back(v[i].first);
  58.             v[i].first = -1;
  59.             continue;
  60.         }
  61.         else if (t == s.begin()) {
  62.             if (*t == v[i].second.first) {
  63.                 //c++;
  64.                 s.erase(v[i].second.first);
  65.                 curr[v[i].first] = *t;
  66.                 //st.push_back(v[i].first);
  67.                 v[i].first = -1;
  68.             }
  69.             else {
  70.                 ans += v[i].second.second;
  71.             }
  72.         }
  73.         else {
  74.             t--;
  75.             s.erase(*t);
  76.             curr[v[i].first] = *t;
  77.             //st.push_back(v[i].first);
  78.             v[i].first = -1;
  79.         }
  80.     }
  81.  
  82.     cout << ans << endl;
  83.  
  84.    
  85.     for (int i = 0; i < n; i++)
  86.         cout << curr[i] << " ";
  87.  
  88.  
  89.     return 0;
  90. }
Advertisement
RAW Paste Data Copied
Advertisement