Submission #1179866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179866		Szymon_Pilipczuk	Advertisement 2 (JOI23_ho_t2)	C++20	100 / 100	742 ms	27716 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define all(a) a.begin(),a.end()
int main()
{
    int n;
    cin>>n;
    vector<pair<int,int>> v;
    for(int i =0 ;i<n;i++)
    {
        int x,e;
        cin>>x>>e;
        v.push_back({e,x});
    }
    sort(all(v));
    reverse(all(v));
    set<pair<int,int>> e;
    for(int i = 0;i<n;i++)
    {
        if(e.find({v[i].nd,v[i].st}) != e.end())
        {
            continue;
        }
        e.insert({v[i].nd,v[i].st});
        auto j = e.find({v[i].nd,v[i].st});
        auto q = e.find({v[i].nd,v[i].st});
        bool c = false;
        if(j != e.begin())
        {
            j--;
            if((*j).nd -v[i].st >= v[i].nd - (*j).st)
            {
                c = true;
            }
        }
        q++;
        if(q != e.end())
        {
            if((*q).nd -v[i].st >= (*q).st - v[i].nd)
            {
                c = true;
            }
        }
        if(c)
        {
            e.erase({v[i].nd,v[i].st});
        }
    }
    cout<<e.size();
}

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