Submission #895551

#	Time	Username	Problem	Language	Result	Execution time	Memory
895551		LiuBruh	Advertisement 2 (JOI23_ho_t2)	C++17	10 / 100	309 ms	21588 KiB

Main

#include <bits/stdc++.h>

#define int long long
#define F first
#define S second
#define sz(v) (int)v.size()
using namespace std;

const int maxn = (int)1005;
const int INF = (int)1e18 + 5;

struct Node
{
    int mnp = INF, mxp = -INF;
};

int n, ord = 0, an = 0;
map<int, Node> mp;

vector<int> e[maxn];
int indeg[maxn];
bitset<maxn> vis;

void sol3() {
    for (int i = 1; i <= n; i++) {
        int x, e;  cin >> x >> e;
        mp[x].mnp = min(mp[x].mnp, e);
        mp[x].mxp = max(mp[x].mxp, e);
    }
    for (auto [pos, node] : mp) {
        ++ord;

        int v = 0;
        for (auto [pos1, node1] : mp) {
            ++v;
            if (pos == pos1) continue;
            if (abs(pos - pos1) <= (node.mxp - node1.mnp)) {
                e[ord].push_back(v);
                ++indeg[v];

                // cout << ord << ' ' << v << '\n';
            }
        }
    }

    queue<int> q;
    vis.set();
    for (int i = 1; i <= ord; i++) {
        if (indeg[i] == 0) q.push(i);
    }
    while (!q.empty()) {
        auto u = q.front();  q.pop();
        if (vis[u]) ++an;
        // cout << "test " << u << '\n';
        for (int v : e[u]) {
            --indeg[v];
            if (vis[u]) vis[v] = false;
            if (indeg[v] == 0) {
                q.push(v);
            }
        }
    }

    cout << an << '\n';
}

set<int> st;

void sol1() {
    for (int i = 1; i <= n; i++) {
        int a, b;  cin >> a >> b;
        st.insert(a);
    }
    cout << sz(st) << '\n';
}

void solve() {
    cin >> n;
    if (n <= 1000) sol3();
    else sol1();
}

/*
4
4 2
2 3
3 4
6 5

3
7 10
7 10
10 10

10
31447678 204745778
430226982 292647686
327782937 367372305
843320852 822224390
687565054 738216211
970840050 766211141
563662348 742939240
103739645 854320982
294864525 601612333
375952316 469655019
*/

signed main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    solve();

    return 0;
}

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