Submission #1281830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281830		hynmj	Advertisement 2 (JOI23_ho_t2)	C++20	100 / 100	1835 ms	155236 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
const long long N = 5e5 + 5;
struct home
{
    int e, x, idx;
};
vector<int> graph[N];
home a[N];
bool vis[N];
void solve()

{
    int n;
    cin >> n;
    vector<pair<int, int>> stak;
    set<int> aa, bb;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i].x >> a[i].e;
        bb.insert(a[i].e);
        aa.insert(a[i].x);
        a[i].idx = i + 1;
    }
    if (bb.size() == 1)
    {
        // cout << "YEAH, done 10 more points";
        cout << aa.size() << endl;
        return;
    }
    sort(a, a + n, [&](home a, home b)
         {if(a.x==b.x)
            return a.e < b.e; 
            return a.x < b.x; });
    int u, v;
    set<pair<int, int>> edges;
    for (int i = 0; i < n; i++)
    {
        u = a[i].idx;
        int e = a[i].x - a[i].e;
        // cout << e << endl;
        while (stak.size() and e <= stak.back().first)
        {
            v = stak.back().second;
            edges.insert({u, v});
            stak.pop_back();
        }
        // e = +a[i].x - a[i].e;
        stak.push_back({e, a[i].idx});
    }

    stak.clear();
    sort(a, a + n, [&](home a, home b)
         {if(a.x==b.x)
            return a.e > b.e;
        return a.x > b.x; });

    for (int i = 0; i < n; i++)
    {
        u = a[i].idx;
        int e = a[i].x + a[i].e;
        while (stak.size() and e >= stak.back().first)
        {
            v = stak.back().second;
            edges.insert({u, v});
            stak.pop_back();
        }

        stak.push_back({e, a[i].idx});
    }

    vector<int> indeg(n + 1, 0);
    for (auto i : edges)
    {
        // cout << i.first << " " << i.second << endl;
        graph[i.first].push_back(i.second);
        indeg[i.second]++;
    }
    queue<int> q;
    for (int i = 0; i < n; i++)
    {
        if (indeg[i + 1] == 0)
        {
            q.push(i + 1);
            // cout << " pushed " << i + 1 << endl;
        }
    }

    int ans = q.size();
    // cout << ans << endl;
    while (q.size())
    {
        int k = q.front();
        // cout << " now visiting  " << k << endl;
        q.pop();
        if (vis[k])
            continue;
        vis[k] = 1;

        for (int i : graph[k])
        {
            if (vis[i] == 0)
                q.push(i);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (!vis[i])
        {
            // cout << "not visited i " << i << endl;
            ans++;
            q.push(i);
            while (q.size())
            {
                int k = q.back();
                q.pop();
                if (vis[k])
                    continue;
                vis[k] = 1;
                for (int i : graph[k])
                {
                    if (!vis[i])
                        q.push(i);
                }
            }
        }
    }
    cout << ans << endl;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++)
    {
        // cout << "Case #" << i << ':' << ' ';
        solve();
        cout << endl;
    }
    return 0;
}

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