Submission #1256319

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256319		Bui_Quoc_Cuong	Advertisement 2 (JOI23_ho_t2)	C++20	59 / 100	2093 ms	16464 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 = 5e5 + 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;
    });
//    FOR(i, 1, n) {
//        cout << line[i].first << " " << line[i].second << "\n";
//    }
    FOR(i, 1, n) {
        FOR(j, 1, i) {
            if (line[j].first <= line[i].first && line[i].second <= line[j].second) {
                g[j].push_back(i);
               /// cout << j << " " << i << "\n";
                break;
            }
        }
    }
    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:75:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:76:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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