Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <map>
- #include <string>
- #include <iomanip>
- #include <algorithm>
- using namespace std;
- using ll = long long;
- using Vector = pair<ll,ll>;
- using Koeff = ll;
- struct Lizard{
- ll x{};
- ll y{};
- ll h{};
- };
- int CeilIndex(std::vector<int>& v, int l, int r, int key)
- {
- while (r - l > 1) {
- int m = l + (r - l) / 2;
- if (v[m] >= key)
- r = m;
- else
- l = m;
- }
- return r;
- }
- int LongestIncreasingSubsequenceLength(std::vector<int>& v)
- {
- if (v.size() == 0)
- return 0;
- std::vector<int> tail(v.size(), 0);
- int length = 1; // always points empty slot in tail
- tail[0] = v[0];
- for (size_t i = 1; i < v.size(); i++) {
- // new smallest value
- if (v[i] < tail[0])
- tail[0] = v[i];
- // v[i] extends largest subsequence
- else if (v[i] > tail[length - 1])
- tail[length++] = v[i];
- // v[i] will become end candidate of an existing
- // subsequence or Throw away larger elements in all
- // LIS, to make room for upcoming greater elements
- // than v[i] (and also, v[i] would have already
- // appeared in one of LIS, identify the location
- // and replace it)
- else
- tail[CeilIndex(tail, -1, length - 1, v[i])] = v[i];
- }
- return length;
- }
- int main() {
- constexpr ll largeK = 1000000000ll;
- Vector tv;
- cin >> tv.first >> tv.second;
- ll n;
- cin >> n;
- map<Koeff , vector<Lizard>> lines;
- for (int i=0;i<n;++i){
- ll x;
- ll y;
- ll h;
- cin >> x >> y >> h;
- ll koeff = (x - tv.first != 0) ? (static_cast<double>(y) - tv.second) / (static_cast<double>(x) - tv.first) * largeK
- : LLONG_MAX;
- lines[koeff].push_back({x,y,h});
- }
- //cout << "**********" << endl;
- vector<vector<pair<ll,ll>>> linesLizard;
- for (auto& line:lines){
- //cout << "--------" << endl;
- vector<pair<ll,ll>> temp;
- for (auto& liz:line.second){
- temp.push_back({liz.x, liz.h});
- }
- temp.push_back({tv.first, 0});
- sort(temp.begin(),temp.end());
- linesLizard.emplace_back(temp);
- //for (auto v:temp)
- // cout << v.first << ' ' << v.second << endl;
- }
- //cout << "************" << endl;
- vector<vector<int>> finalLizard;
- for (auto& line:linesLizard){
- vector<int> temp;
- for (auto& liz:line){
- if (liz.second==0){
- reverse(temp.begin(),temp.end());
- if (!temp.empty())
- finalLizard.emplace_back(temp);
- temp.clear();
- continue;
- }
- temp.push_back(liz.second);
- }
- if (!temp.empty())
- finalLizard.emplace_back(temp);
- }
- ll ans = 0;
- for (auto& line:finalLizard){
- int len = LongestIncreasingSubsequenceLength(line);
- //cout << len << endl;
- ans+=len;
- }
- cout << ans << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement