Submission #1360616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1360616		rukashii	Advertisement 2 (JOI23_ho_t2)	C++20	10 / 100	479 ms	88016 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define file                                \
    if (fopen("input.txt", "r"))            \
    {                                       \
        freopen("input.txt", "r", stdin);   \
        freopen("output.txt", "w", stdout); \
    }
#define int long long
#define x first
#define e second

void setIn(string s) { freopen(s.c_str(), "r", stdin); }
void setOut(string s) { freopen(s.c_str(), "w", stdout); }
void setIO(string s = "")
{
    if (s.size())
        setIn(s + ".inp"), setOut(s + ".out");
}

const int maxn = 5e5 + 2;

vector<int> adj[maxn];
bool vis[maxn];

void dfs(int u)
{
    vis[u] = 1;
    for (int v : adj[u])
    {
        if (vis[v])
            continue;

        dfs(v);
    }
}

void solve()
{
    int n;
    cin >> n;

    vector<pair<int, int>> a(n + 2);
    vector<int> deg(n + 2, 0);
    for (int i = 1; i <= n; i++)
        cin >> a[i].x >> a[i].e;

    sort(a.begin() + 1, a.begin() + 1 + n);

    // for (int i = 1; i <= n; i++)
    //     cout << a[i].x << ' ' << a[i].e << '\n';
    // cout << '\n';

    set<pair<int, int>> nL, nR;

    for (int i = 1; i <= n; i++)
        nR.insert({a[i].x + a[i].e, i});

    for (int i = 1; i <= n; i++)
    {
        nR.erase(nR.find({a[i].x + a[i].e, i}));

        auto it = nL.upper_bound({a[i].e - a[i].x, INT_MAX});
        if (it != nL.begin())
        {
            auto [val, pos] = *(--it);
            deg[pos]++;
            adj[i].push_back(pos);
        }
        auto it2 = nR.upper_bound({a[i].e + a[i].x, INT_MAX});
        if (it2 != nR.begin())
        {
            auto [val, pos] = *(--it2);
            deg[pos]++;
            adj[i].push_back(pos);
            // cout << "2 " << i << ' ' << pos << '\n';
        }

        nL.insert({a[i].e - a[i].x, i});
    }

    vector<pair<int, int>> cur;
    for (int i = 1; i <= n; i++)
        cur.push_back({deg[i], i});
    sort(cur.begin(), cur.end());

    int ans = 0;
    for (auto [d, u] : cur)
        if (!vis[u])
            ans++, dfs(u);

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

signed main()
{
    // setIO();
    file;
    ios::sync_with_stdio(0);
    cin.tie(0);

    solve();
}

Compilation message (stderr)

Main.cpp: In function 'void setIn(std::string)':
Main.cpp:14:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 | void setIn(string s) { freopen(s.c_str(), "r", stdin); }
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'void setOut(std::string)':
Main.cpp:15:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 | void setOut(string s) { freopen(s.c_str(), "w", stdout); }
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:7:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |         freopen("input.txt", "r", stdin);   \
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:99:5: note: in expansion of macro 'file'
   99 |     file;
      |     ^~~~
Main.cpp:8:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |         freopen("output.txt", "w", stdout); \
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:99:5: note: in expansion of macro 'file'
   99 |     file;
      |     ^~~~

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