Advertisement
dmkozyrev

Untitled

Jul 21st, 2018
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.57 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <set>
  5.  
  6. typedef long long ll;
  7.  
  8. struct Pair {
  9.     int x, y;
  10. };
  11.  
  12. int main() {
  13.     freopen("input.txt", "rt", stdin);
  14.    
  15.     //std::ios_base_sync_with_stdio(false);
  16.     //std::cin.tie(0); std::cout.tie(0); std::cerr.tie(0);
  17.    
  18.     int n, limit; std::cin >> n >> limit;
  19.    
  20.     auto cmpx = [](const Pair& a, const Pair& b){
  21.         return a.x < b.x || (a.x == b.x && a.y < b.y);
  22.     };
  23.    
  24.     auto cmpy = [](const Pair& a, const Pair& b){
  25.         return a.y < b.y || (a.y == b.y && a.x < b.x);
  26.     };
  27.    
  28.     std::vector<Pair> ordered_x, ordered_y;
  29.     for (int i = 0; i < n; ++i) {
  30.         int x, y; std::cin >> x >> y;
  31.         ordered_x.push_back(Pair{x,y});
  32.         ordered_y.push_back(Pair{x,y});
  33.     }
  34.     std::sort(ordered_x.begin(), ordered_x.end(), cmpx);
  35.     std::sort(ordered_y.begin(), ordered_y.end(), cmpy);
  36.    
  37.     std::multiset<Pair, decltype(cmpx)> set(cmpx);
  38.     ll answ = 0;
  39.     for (int i = 0; i < n; ++i) {
  40.         while ((int)set.size() < limit && !ordered_x.empty()) {
  41.             auto p = ordered_x.back(); ordered_x.pop_back();
  42.             if (p.y < ordered_y[i].y) continue;
  43.             set.insert(p);
  44.         }
  45.         if ((int)set.size() == limit) {
  46.             for (auto& it : set) {
  47.                 std::cout << it.x << ' ' << it.y << std::endl;
  48.             }
  49.             answ = std::max(answ, (ll) set.begin()->x * ordered_y[i].y);
  50.             std::cout << "answ = " << answ << std::endl << std::string(80, '-') << std::endl;
  51.         }
  52.         if (i == 0 || ordered_y[i].y == ordered_y[i-1].y) {
  53.             continue;
  54.         }
  55.         for (int j = i-1; j >= 0 && ordered_y[j].y == ordered_y[i-1].y; --j) {
  56.             if (set.find(ordered_y[j]) != set.end()) {
  57.                 set.erase(ordered_y[j]);
  58.             }
  59.         }  
  60.     }
  61.     std::cout << answ;
  62.     return 0;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement