이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |