제출 #780928

#제출 시각아이디문제언어결과실행 시간메모리
780928boris_mihovAdvertisement 2 (JOI23_ho_t2)C++17
59 / 100
108 ms12304 KiB
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <stack>
#include <set>

typedef long long llong;
const int MAXN = 200000 + 10;
const int INF  = 1e9;

struct Person
{
    int x, e;
    friend bool operator > (const Person &a, const Person &b)
    {
        return a.e > b.e;
    }
};

int n;
Person p[MAXN];
std::set <std::pair <int,int>> left, right;

void solve()
{
    int ans = 0;
    std::sort(p + 1, p + 1 + n, std::greater <Person> ());
    
    for (int i = 1 ; i <= n ; ++i)
    {
        bool thereIs = false;
        
        auto it = left.lower_bound({p[i].e - p[i].x, 0});
        if (it != left.end() && it->second >= p[i].x)
        {
            thereIs = true;
        }

        it = right.lower_bound({p[i].x + p[i].e, 0});
        if (it != right.end() && it->second <= p[i].x)
        {
            thereIs = true;
        }
        
        if (!thereIs)
        {
            ans++;
            // while (left.size())
            // {
            //     auto it = left.lower_bound({p[i].e - p[i].x, 0});
            //     if (it != left.end() && it->second <= p[i].x)
            //     {
            //         left.erase(it);
            //     } else
            //     {
            //         break;
            //     }
            // }

            left.insert({p[i].e - p[i].x, p[i].x});

            // while (right.size())
            // {
            //     auto it = right.lower_bound({p[i].x + p[i].x, 0});
            //     if (it != right.end() && it->second >= p[i].x)
            //     {
            //         right.erase(it);
            //     } else
            //     {
            //         break;
            //     }
            // }

            right.insert({p[i].x + p[i].e, p[i].x});
        }
    }

    std::cout << ans << '\n';
}   

void input()
{
    std::cin >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> p[i].x >> p[i].e;
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...