Submission #1256320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256320		Bui_Quoc_Cuong	Advertisement 2 (JOI23_ho_t2)	C++20	100 / 100	622 ms	86196 KiB

Main

#include <bits/stdc++.h>
using namespace std;
template <class T1, class T2>
    bool maximize (T1 &a, T2 b) {
        if (a < b) {a = b; return true;}
        return false;
    }
template <class T1, class T2>
    bool minimize (T1 &a, T2 b) {
        if (a > b) {a = b; return true;}
        return false;
    }
#define FOR(i, a, b) for(int i = a; i <= (int)b; i++)
#define FORD(i, a, b) for(int i = a; i >= (int)b; i--)
#define MASK(i) (1LL << (i))
#define BIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
const int MAXN = 1e6 + 5;

int n;
array <int, 2> a[MAXN];

void init(void) {
    cin >> n;
    FOR(i, 1, n) cin >> a[i][0] >> a[i][1];
    sort (a + 1, a + 1 + n);
}

pair <int, int> line[MAXN];
vector <int> g[MAXN];
bool vis[MAXN];

void dfs(int u) {
    if (vis[u]) return;
    vis[u] = 1;
    for (int &v : g[u]) {
        dfs(v);
    }
}

void process(void) {
    FOR(i, 1, n) {
        line[i].first = a[i][0] - a[i][1];
        line[i].second = a[i][0] +  a[i][1];
    }
    sort (line + 1, line + 1 + n, [&] (pair <int, int> u, pair <int, int> v) {
        if (u.first == v.first) return u.second > v.second;
        return u.first < v.first;
    });
    vector <int> values;
    FOR(i, 1, n) {
        values.push_back(line[i].first);
        values.push_back(line[i].second);
    }
    sort(ALL(values)); values.resize(unique(ALL(values)) - values.begin());
    FOR(i, 1, n) {
        line[i].first = upper_bound(ALL(values), line[i].first) - values.begin();
        line[i].second = upper_bound(ALL(values), line[i].second) - values.begin();
    }
    set <pair <int, int>> se;
    FOR(i, 1, n) {
        if (!se.empty()) {
            if (se.rbegin() -> first >= line[i].second) {
                int id = se.rbegin() -> second;
                g[id].push_back(i);
            }
        }
        se.insert(make_pair(line[i].second, i));
    }
    int ans = 0;
    FOR(i, 1, n) if (!vis[i]) {
        ans++;
        dfs(i);
    }
    cout << ans;
}

signed main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #define taskname "kieuoanh"
    if (fopen(taskname".inp", "r")) {
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    init();
    process();

    cerr << "\n[Time elapsed] " << clock() << " ms!\n";
    return 0;
}
/*
4
4 2
2 3
3 4
6 5
*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:83:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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