Submission #1187193

#TimeUsernameProblemLanguageResultExecution timeMemory
1187193DedibeatAdvertisement 2 (JOI23_ho_t2)C++20
0 / 100
1 ms328 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; vector<int> t; void upd(int v, int tl, int tr, int pos, int val) { if(tl == tr) t[v] += val; else { int tm = (tl + tr) / 2; if(pos <= tm) upd(2 * v, tl, tm, pos, val); else upd(2 * v + 1, tm + 1, tr, pos, val); t[v] = t[2 * v] + t[2 * v + 1]; } } int get(int v, int tl, int tr, int l, int r) { if(l > r) return 0; if(tl == l && tr == r) return t[v]; else { int tm = (tl + tr) / 2; return get(2 * v, tl, tm, l, min(r, tm)) + get(2 * v + 1, tm + 1, tr, max(l, tm + 1), r); } } void comp(vector<int> &v) { map<int, int> mp; for(int &x : v) mp[x] = 1, cout << x << "\n"; int cnt = 0; for(auto &[f, s] : mp) s = cnt++; for(int &x : v) x = mp[x], cout << x << "\n"; } int main() { int n; cin >> n; vector<pair<int, int>> v(n); for(auto &[x, y] : v) cin >> x >> y; sort(v.begin(), v.end()); vector<int> vec1, vec2; for(auto &[x, y] : v) { vec1.push_back(x - y); vec2.push_back(x + y); } set<int> st; vector<int> cnt(n, 0); for(int i = 0; i < n; i++) { auto it = st.lower_bound(vec2[i]); if(it != st.end()) cnt[i] = 1; st.insert(vec2[i]); } st.clear(); for(int i = n - 1; i >= 0; i--) { auto it = st.lower_bound(-vec1[i]); if(it != st.end()) cnt[i] = 1; st.insert(-vec1[i]); } int ans = 0; for(int i = 0; i < n; i++) if(cnt[i] == 0) ans++; cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...