Submission #769065

#	Time	Username	Problem	Language	Result	Execution time	Memory
769065		danikoynov	Advertisement 2 (JOI23_ho_t2)	C++14	100 / 100	623 ms	34688 KiB

Main

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 5e5 + 10;

struct point
{
    int x, y;
} p[maxn];

bool cmp(const point &p1, const point &p2)
{
    return p1.y > p2.y;
}

int n;
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> p[i].x >> p[i].y;
    }

    sort(p + 1, p + n + 1, cmp);
    int ans = 0;
    set < pair < int, int > > st;
    for (int i = 1; i <= n; i ++)
    {
        pair < int, int > cur = {p[i].x, i};
        st.insert(cur);
        set < pair < int, int > > :: iterator it = st.find(cur), hp;
        bool covered = false;
        if (it != st.begin())
        {
            hp = prev(it);
            if (cur.first - hp -> first <= p[hp -> second].y - p[cur.second].y)
                covered = true;
        }
        if (next(it) != st.end())
        {
            hp = next(it);
            if (hp -> first - cur.first <= p[hp -> second].y - p[cur.second].y)
                covered = true;
        }
        if (!covered)
            ans ++;
        else
            st.erase(it);
    }

    cout << ans << endl;
}

int main()
{
    solve();
    return 0;
}

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