Submission #780937

#	Time	Username	Problem	Language	Result	Execution time	Memory
780937		boris_mihov	Advertisement 2 (JOI23_ho_t2)	C++17	59 / 100	133 ms	7048 KiB

Main

#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.upper_bound({p[i].e - p[i].x, 0});
                if (it != left.begin() && std::prev(it)->second <= p[i].x)
                {
                    left.erase(std::prev(it));
                } else
                {
                    break;
                }
            }

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

            while (right.size())
            {
                auto it = right.upper_bound({p[i].x + p[i].x, 0});
                if (it != right.begin() && std::prev(it)->second >= p[i].x)
                {
                    right.erase(std::prev(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;
}

• Subtask 1: 0 / 10
• Subtask 2: 23 / 23
• Subtask 3: 36 / 36
• Subtask 4: 0 / 31