Advertisement
atrem21215

Untitled

Oct 2nd, 2022
757
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.13 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <string>
  5. #include <iomanip>
  6. #include <algorithm>
  7. using namespace std;
  8. using ll = long long;
  9. using Vector = pair<ll,ll>;
  10. using Koeff = ll;
  11. struct Lizard{
  12.     ll x{};
  13.     ll y{};
  14.     ll h{};
  15. };
  16.  
  17. int CeilIndex(std::vector<int>& v, int l, int r, int key)
  18. {
  19.     while (r - l > 1) {
  20.         int m = l + (r - l) / 2;
  21.         if (v[m] >= key)
  22.             r = m;
  23.         else
  24.             l = m;
  25.     }
  26.  
  27.     return r;
  28. }
  29.  
  30. int LongestIncreasingSubsequenceLength(std::vector<int>& v)
  31. {
  32.     if (v.size() == 0)
  33.         return 0;
  34.  
  35.     std::vector<int> tail(v.size(), 0);
  36.     int length = 1; // always points empty slot in tail
  37.  
  38.     tail[0] = v[0];
  39.     for (size_t i = 1; i < v.size(); i++) {
  40.  
  41.         // new smallest value
  42.         if (v[i] < tail[0])
  43.             tail[0] = v[i];
  44.  
  45.             // v[i] extends largest subsequence
  46.         else if (v[i] > tail[length - 1])
  47.             tail[length++] = v[i];
  48.  
  49.             // v[i] will become end candidate of an existing
  50.             // subsequence or Throw away larger elements in all
  51.             // LIS, to make room for upcoming greater elements
  52.             // than v[i] (and also, v[i] would have already
  53.             // appeared in one of LIS, identify the location
  54.             // and replace it)
  55.         else
  56.             tail[CeilIndex(tail, -1, length - 1, v[i])] = v[i];
  57.     }
  58.  
  59.     return length;
  60. }
  61.  
  62.  
  63. int main() {
  64.     constexpr ll largeK = 1000000000ll;
  65.     Vector tv;
  66.     cin >> tv.first >> tv.second;
  67.     ll n;
  68.     cin >> n;
  69.     map<Koeff , vector<Lizard>> lines;
  70.     for (int i=0;i<n;++i){
  71.         ll x;
  72.         ll y;
  73.         ll h;
  74.         cin >> x >> y >> h;
  75.         ll koeff = (x - tv.first != 0) ? (static_cast<double>(y) - tv.second) / (x - tv.first) * largeK
  76.                                        : 981239184929192ll;
  77.         lines[koeff].push_back({x,y,h});
  78.     }
  79.  
  80.     //cout << "**********" << endl;
  81.     vector<vector<pair<ll,ll>>> linesLizard;
  82.     for (auto& line:lines){
  83.         //cout << "--------" << endl;
  84.         vector<pair<ll,ll>> temp;
  85.         for (auto& liz:line.second){
  86.             temp.push_back({liz.x, liz.h});
  87.         }
  88.         temp.push_back({tv.first, 0});
  89.         sort(temp.begin(),temp.end());
  90.         linesLizard.emplace_back(temp);
  91.         //for (auto v:temp)
  92.           //  cout << v.first << ' ' << v.second << endl;
  93.     }
  94.     //cout << "************" << endl;
  95.  
  96.     vector<vector<int>> finalLizard;
  97.  
  98.     for (auto& line:linesLizard){
  99.         vector<int> temp;
  100.         for (auto& liz:line){
  101.             if (liz.second==0){
  102.                 reverse(temp.begin(),temp.end());
  103.                 if (!temp.empty())
  104.                     finalLizard.emplace_back(temp);
  105.                 temp.clear();
  106.                 continue;
  107.             }
  108.             temp.push_back(liz.second);
  109.         }
  110.         if (!temp.empty())
  111.             finalLizard.emplace_back(temp);
  112.     }
  113.  
  114.     ll ans = 0;
  115.     for (auto& line:finalLizard){
  116.         int len = LongestIncreasingSubsequenceLength(line);
  117.         //cout << len << endl;
  118.         ans+=len;
  119.     }
  120.     cout << ans << endl;
  121.  
  122.  
  123. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement