Advertisement
OIQ

XD

OIQ
Nov 28th, 2019
193
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.43 KB | None
  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.  
  45.     vector <int> st;
  46.     long long ans = 0;
  47.  
  48.     for (int i = 0; i < n; i++) {
  49.         auto t = s.lower_bound(v[i].second.first);
  50.         if (*t == v[i].second.first) {
  51.             s.erase(v[i].second.first);
  52.             st.push_back(v[i].first);
  53.             v[i].first = -1;
  54.             continue;
  55.         }
  56.         else if (t == s.begin()) {
  57.             if (*t == v[i].second.first) {
  58.                 s.erase(v[i].second.first);
  59.                 st.push_back(v[i].first);
  60.                 v[i].first = -1;
  61.             }
  62.             else {
  63.                 ans += v[i].second.second;
  64.             }
  65.         }
  66.         else {
  67.             t--;
  68.             s.erase(*t);
  69.             st.push_back(v[i].first);
  70.             v[i].first = -1;
  71.         }
  72.     }
  73.  
  74.     cout << ans << endl;
  75.     for (int i = 0; i < st.size(); i++)
  76.         cout << st[i] + 1<< " ";
  77.  
  78.     for (int i = 0; i < n; i++)
  79.         if (v[i].first != -1)
  80.             cout << v[i].first + 1 << " ";
  81.  
  82.     return 0;
  83. }
Advertisement
RAW Paste Data Copied
Advertisement